CSES - Aalto Competitive Programming 2024 - wk6 - Wed - Results
Submission details
Task:Online feud
Sender:aalto2024g_007
Submission time:2024-10-09 17:12:12 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#140.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#170.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#240.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#270.00 sdetails
#28ACCEPTED0.00 sdetails
#290.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#350.00 sdetails
#36ACCEPTED0.00 sdetails
#370.00 sdetails
#38ACCEPTED0.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#42ACCEPTED0.00 sdetails
#43ACCEPTED0.00 sdetails
#44ACCEPTED0.00 sdetails
#450.00 sdetails
#46ACCEPTED0.00 sdetails
#470.00 sdetails
#48ACCEPTED0.01 sdetails
#490.00 sdetails
#500.00 sdetails
#510.00 sdetails
#52ACCEPTED0.01 sdetails
#53ACCEPTED0.01 sdetails
#54ACCEPTED0.01 sdetails
#550.01 sdetails
#56ACCEPTED0.01 sdetails
#570.01 sdetails
#58ACCEPTED0.01 sdetails
#590.01 sdetails
#600.01 sdetails
#610.01 sdetails
#62ACCEPTED0.32 sdetails
#63ACCEPTED0.28 sdetails
#640.34 sdetails
#650.32 sdetails
#66ACCEPTED0.50 sdetails
#670.22 sdetails
#68ACCEPTED0.44 sdetails
#690.17 sdetails
#700.46 sdetails
#710.15 sdetails

Code

// ~/.vim/cpp_template.cpp
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>

#define REP(i,a,b) for (int i = a; i < b; i++)

// Type Aliases for 1D and 2D vectors with initialization
#define vi(n, val) vector<int>(n, val) // 1D vector of ints with size n, initialized to val
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

#define LL_INF std::numeric_limits<long long int>::max()
#define INF std::numeric_limits<int>::max()


using namespace std;


template <typename T>
void pV(const std::vector<T>& vec, const std::string& label = "Vector") {
    std::cout << label << ": [ ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << "]" << std::endl;
}


void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {
    if ((*visited)[s]) return;
    (*visited)[s] = true;
    // process node s


    for (auto u: (*adj)[s]) {
        dfs(u, visited, adj);
    }
}
/*
// DEPTH-FRIRST-SEARCH
vector<int> adj[N];                                                          
vector<bool> visited(N, false);
int u, v;
for(int i = 0; i < M;i++){
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
*/

vector<long long> dijkstra(int N, int x, vector<vector<pair<int,int>>> *adj){
    vector<bool> processed(N, false);
    vector<long long> distance(N, LL_INF);
    priority_queue<pair<long long,int>> q;
    //for (int i = 1; i <= n; i++) distance[i] = INF;
    distance[x] = 0;
    q.push({0,x});
    while (!q.empty()) {
        int a = q.top().second; q.pop();
        if (processed[a]) continue;
        processed[a] = true;
        for (auto u : (*adj)[a]) {
            int b = u.first, w = u.second;
            if (distance[a]+w < distance[b]) {
                distance[b] = distance[a]+w;
                q.push({-distance[b],b});
            }
        }
    }
    return distance;


}


/*
DIJKSTRA
//vector<vector<pair<int,int>>> adj(N, vector<pair<int, int>>(N));
*/



int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // Your code starts here
    int n, m;
    cin >> n >> m;

    map<int, set<int>> like;
    map<int, set<int>> dislike;

    REP(i, 0, m){
        int a, b, c;
        cin >> a >> b >> c;
        if(c == 1){
            like[a].insert(b);
            like[b].insert(a);
        }else{
            dislike[a].insert(b);
            dislike[b].insert(a);
        }
    }

    set<int> open;

    // sol
    set<int> left, right;
    left.insert(1);
    for(auto x: like[1]){
        left.insert(x);
    }
    for(auto x: dislike[1]){
        right.insert(x);
    }
    
    REP(i, 2, n+1){
        /*
        if(left.count(i)){
            left.insert(like[i].begin(), like[i].end());
            continue;
        }
        if(right.count(i)){
            right.insert(dislike[i].begin(), dislike[i].end());
            continue;
        }
        */
        for(auto x: like[i]){
            if(left.count(x)){
                left.insert(i);
            }else if(right.count(x)){
                right.insert(i);
            }else{
                open.insert(i);
            }
            if(left.count(i) && right.count(i)){
                cout << "No" << endl;
                exit(0);
            }
        }
        for(auto x: dislike[i]){
            if(left.count(x)){
                right.insert(i);
            }else if(right.count(x)){
                left.insert(i);
            }else{
                open.insert(i);
            }
            if(left.count(i) && right.count(i)){
                cout << "No" << endl;
                exit(0);
            }
        }
    }

    for(auto i: open){
        for(auto x: like[i]){
            if(left.count(x)){
                left.insert(i);
            }else{
                right.insert(i);
            }
            if(left.count(i) && right.count(i)){
                cout << "No" << endl;
                exit(0);
            }
        }
        for(auto x: dislike[i]){
            if(left.count(x)){
                right.insert(i);
            }else{
                left.insert(i);
            }
            if(left.count(i) && right.count(i)){
                cout << "No" << endl;
                exit(0);
            }
        }

    }

    cout << "Yes" << endl;


    return 0;
}


Test details

Test 1

Verdict: ACCEPTED

input
2 4
2 1 1
1 2 -1
1 2 1
1 2 -1

correct output
No

user output
No

Test 2

Verdict: ACCEPTED

input
2 4
1 2 -1
2 1 -1
1 2 -1
1 2 -1

correct output
Yes

user output
Yes

Test 3

Verdict: ACCEPTED

input
3 2
2 3 1
3 2 1

correct output
Yes

user output
Yes

Test 4

Verdict: ACCEPTED

input
3 4
3 1 -1
2 1 -1
2 1 -1
1 2 -1

correct output
Yes

user output
Yes

Test 5

Verdict: ACCEPTED

input
3 5
1 2 1
3 2 -1
3 2 1
3 2 1
...

correct output
No

user output
No

Test 6

Verdict: ACCEPTED

input
4 3
4 1 -1
1 2 1
2 4 -1

correct output
Yes

user output
Yes

Test 7

Verdict: ACCEPTED

input
4 8
3 4 1
1 3 -1
2 3 -1
1 2 1
...

correct output
Yes

user output
Yes

Test 8

Verdict: ACCEPTED

input
4 8
3 2 -1
3 1 -1
1 2 1
1 2 1
...

correct output
Yes

user output
Yes

Test 9

Verdict: ACCEPTED

input
4 7
3 4 1
3 2 -1
2 1 1
1 4 -1
...

correct output
No

user output
No

Test 10

Verdict: ACCEPTED

input
4 8
3 1 -1
1 2 1
4 3 1
1 2 -1
...

correct output
No

user output
No

Test 11

Verdict: ACCEPTED

input
4 7
1 3 -1
4 2 1
3 4 1
4 2 -1
...

correct output
No

user output
No

Test 12

Verdict: ACCEPTED

input
5 7
4 5 -1
5 3 -1
3 4 -1
2 3 1
...

correct output
No

user output
No

Test 13

Verdict: ACCEPTED

input
5 6
4 5 1
1 2 -1
1 2 1
2 1 1
...

correct output
No

user output
No

Test 14

Verdict:

input
5 6
4 5 1
1 3 1
4 5 1
2 4 1
...

correct output
Yes

user output
No

Test 15

Verdict: ACCEPTED

input
5 7
4 5 1
1 3 1
1 4 -1
1 4 -1
...

correct output
Yes

user output
Yes

Test 16

Verdict: ACCEPTED

input
5 10
3 1 -1
5 4 -1
4 3 1
1 5 1
...

correct output
No

user output
No

Test 17

Verdict:

input
5 4
4 5 -1
5 3 -1
3 5 -1
3 4 1

correct output
Yes

user output
No

Test 18

Verdict: ACCEPTED

input
5 10
1 5 -1
1 3 -1
3 4 -1
3 4 -1
...

correct output
Yes

user output
Yes

Test 19

Verdict: ACCEPTED

input
5 3
5 2 -1
4 3 -1
2 4 -1

correct output
Yes

user output
Yes

Test 20

Verdict: ACCEPTED

input
5 9
5 4 -1
1 5 -1
3 5 -1
1 3 1
...

correct output
Yes

user output
Yes

Test 21

Verdict: ACCEPTED

input
5 3
1 3 -1
1 3 -1
3 4 1

correct output
Yes

user output
Yes

Test 22

Verdict: ACCEPTED

input
10 14
8 9 -1
9 6 -1
5 7 -1
4 5 1
...

correct output
No

user output
No

Test 23

Verdict: ACCEPTED

input
10 12
8 10 1
2 4 -1
2 3 1
4 2 1
...

correct output
No

user output
No

Test 24

Verdict:

input
10 12
9 10 1
2 5 1
8 10 1
5 8 1
...

correct output
Yes

user output
No

Test 25

Verdict: ACCEPTED

input
10 14
8 10 1
3 7 1
1 8 -1
1 8 -1
...

correct output
Yes

user output
Yes

Test 26

Verdict: ACCEPTED

input
10 20
6 2 -1
9 8 -1
7 6 1
2 10 1
...

correct output
No

user output
No

Test 27

Verdict:

input
10 9
9 10 1
9 10 1
9 7 -1
3 10 -1
...

correct output
Yes

user output
No

Test 28

Verdict: ACCEPTED

input
10 19
4 3 -1
2 10 -1
1 6 -1
5 6 1
...

correct output
No

user output
No

Test 29

Verdict:

input
10 7
10 4 -1
8 7 -1
4 8 -1
2 8 -1
...

correct output
Yes

user output
No

Test 30

Verdict: ACCEPTED

input
10 19
10 8 -1
1 10 -1
5 10 -1
2 6 1
...

correct output
Yes

user output
Yes

Test 31

Verdict: ACCEPTED

input
10 6
3 6 -1
1 6 -1
6 7 1
1 7 -1
...

correct output
Yes

user output
Yes

Test 32

Verdict: ACCEPTED

input
100 133
72 85 -1
86 55 -1
43 63 -1
39 44 1
...

correct output
No

user output
No

Test 33

Verdict: ACCEPTED

input
100 113
73 94 1
13 31 -1
15 24 1
40 19 1
...

correct output
No

user output
No

Test 34

Verdict: ACCEPTED

input
100 116
1 2 1
1 34 -1
71 1 -1
1 50 -1
...

correct output
Yes

user output
Yes

Test 35

Verdict:

input
100 133
74 88 1
31 66 1
9 72 -1
4 73 -1
...

correct output
Yes

user output
No

Test 36

Verdict: ACCEPTED

input
100 196
55 18 -1
86 72 -1
70 60 1
15 98 1
...

correct output
No

user output
No

Test 37

Verdict:

input
100 84
92 100 1
89 96 1
92 67 -1
26 100 -1
...

correct output
Yes

user output
No

Test 38

Verdict: ACCEPTED

input
100 184
34 21 -1
7 5 1
11 99 -1
10 53 -1
...

correct output
No

user output
No

Test 39

Verdict:

input
100 62
100 34 -1
85 76 -1
39 79 -1
21 78 -1
...

correct output
Yes

user output
No

Test 40

Verdict:

input
100 182
98 84 -1
98 99 1
99 100 1
51 100 -1
...

correct output
Yes

user output
No

Test 41

Verdict:

input
100 52
25 51 -1
8 51 -1
57 68 1
5 70 -1
...

correct output
Yes

user output
No

Test 42

Verdict: ACCEPTED

input
200 265
144 169 -1
172 109 -1
85 125 -1
77 88 1
...

correct output
No

user output
No

Test 43

Verdict: ACCEPTED

input
200 226
145 187 1
26 61 -1
30 48 1
80 38 1
...

correct output
No

user output
No

Test 44

Verdict: ACCEPTED

input
200 231
4 5 1
3 68 -1
142 2 -1
2 100 -1
...

correct output
Yes

user output
Yes

Test 45

Verdict:

input
200 266
149 176 1
62 133 1
18 144 -1
8 147 -1
...

correct output
Yes

user output
No

Test 46

Verdict: ACCEPTED

input
200 391
110 35 -1
172 143 -1
140 120 1
29 196 1
...

correct output
No

user output
No

Test 47

Verdict:

input
200 167
184 199 1
177 192 1
184 134 -1
52 200 -1
...

correct output
Yes

user output
No

Test 48

Verdict: ACCEPTED

input
200 368
67 42 -1
13 9 1
22 198 -1
20 106 -1
...

correct output
No

user output
No

Test 49

Verdict:

input
200 123
200 68 -1
169 152 -1
78 159 -1
42 156 -1
...

correct output
Yes

user output
No

Test 50

Verdict:

input
200 363
196 168 -1
196 197 1
198 199 1
101 200 -1
...

correct output
Yes

user output
No

Test 51

Verdict:

input
200 104
50 101 -1
15 102 -1
114 136 1
9 140 -1
...

correct output
Yes

user output
No

Test 52

Verdict: ACCEPTED

input
1000 1324
716 845 -1
858 545 -1
424 624 -1
385 438 1
...

correct output
No

user output
No

Test 53

Verdict: ACCEPTED

input
1000 1126
721 933 1
129 303 -1
147 237 1
397 187 1
...

correct output
No

user output
No

Test 54

Verdict: ACCEPTED

input
1000 1154
23 24 1
11 338 -1
707 6 -1
8 499 -1
...

correct output
Yes

user output
Yes

Test 55

Verdict:

input
1000 1327
744 875 1
310 667 1
89 720 -1
37 736 -1
...

correct output
Yes

user output
No

Test 56

Verdict: ACCEPTED

input
1000 1951
548 173 -1
856 715 -1
698 598 1
142 977 1
...

correct output
No

user output
No

Test 57

Verdict:

input
1000 833
917 994 1
882 955 1
917 667 -1
259 999 -1
...

correct output
Yes

user output
No

Test 58

Verdict: ACCEPTED

input
1000 1840
332 210 -1
65 42 1
108 986 -1
100 530 -1
...

correct output
No

user output
No

Test 59

Verdict:

input
1000 615
996 342 -1
848 762 -1
391 799 -1
210 783 -1
...

correct output
Yes

user output
No

Test 60

Verdict:

input
1000 1811
981 842 -1
982 983 1
992 996 1
506 996 -1
...

correct output
Yes

user output
No

Test 61

Verdict:

input
1000 516
249 505 -1
72 508 -1
570 677 1
43 699 -1
...

correct output
Yes

user output
No

Test 62

Verdict: ACCEPTED

input
100000 132323
71521 84428 -1
85796 54490 -1
42367 62358 -1
38439 43760 1
...

correct output
No

user output
No

Test 63

Verdict: ACCEPTED

input
100000 112554
72034 93258 1
12813 30234 -1
14676 23610 1
39659 18627 1
...

correct output
No

user output
No

Test 64

Verdict:

input
100000 115400
2456 2516 1
1090 33816 -1
70668 531 -1
777 49853 -1
...

correct output
Yes

user output
No

Test 65

Verdict:

input
100000 132621
74356 87456 1
30951 66681 1
8894 72001 -1
3645 73546 -1
...

correct output
Yes

user output
No

Test 66

Verdict: ACCEPTED

input
100000 195056
54725 17270 -1
85564 71483 -1
69774 59757 1
14147 97629 1
...

correct output
No

user output
No

Test 67

Verdict:

input
100000 83300
91776 99331 1
88235 95433 1
91652 66692 -1
25844 99882 -1
...

correct output
Yes

user output
No

Test 68

Verdict: ACCEPTED

input
100000 183930
33199 20941 -1
6426 4170 1
10766 98505 -1
9948 52983 -1
...

correct output
No

user output
No

Test 69

Verdict:

input
100000 61447
99521 34194 -1
84772 76278 -1
39085 79902 -1
20937 78344 -1
...

correct output
Yes

user output
No

Test 70

Verdict:

input
100000 181015
98043 84187 -1
98183 98204 1
99264 99561 1
50624 99598 -1
...

correct output
Yes

user output
No

Test 71

Verdict:

input
100000 51557
24883 50564 -1
7133 50852 -1
57039 67698 1
4219 69908 -1
...

correct output
Yes

user output
No