# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
411540 | 2021-05-25T13:26:47 Z | Ruxandra985 | Graph (BOI20_graph) | C++14 | 103 ms | 10280 KB |
#include <bits/stdc++.h> #define DIMN 100010 using namespace std; double sol[DIMN]; int f[DIMN] , f2[DIMN]; vector <pair <int , int> > v[DIMN]; vector <int> taken; pair <int , int> cod[DIMN]; deque <int> dq; int main() { FILE *fin = stdin; FILE *fout = stdout; int n , m , i , a , y , z , found , nod , vecin , tip , mini , poz , sum; double x; fscanf (fin,"%d%d",&n,&m); for (i = 1 ; i <= m ; i++){ fscanf (fin,"%d%d%d",&a,&y,&z); v[a].push_back(make_pair(y , z)); v[y].push_back(make_pair(a , z)); } for (int j = 1 ; j <= n ; j++){ if (f2[j]) continue; cod[j] = make_pair(0 , 1); dq.push_back(j); f[j] = 1; found = 0; taken.clear(); while (!dq.empty() && !found){ nod = dq.front(); dq.pop_front(); taken.push_back(nod); for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; tip = v[nod][i].second; if (!f[vecin]){ dq.push_back(vecin); f[vecin] = 1; cod[vecin] = make_pair(tip - cod[nod].first , -cod[nod].second); } else { /// momentul sa vezi daca relatiile sunt echivalente, contradictorii /// sau daca sau solutia x if (cod[vecin] == make_pair(tip - cod[nod].first , -cod[nod].second)) continue; /// echivalent if (cod[vecin].second == -cod[nod].second && cod[vecin].first != tip - cod[nod].first){ fprintf (fout,"NO"); /// contradictorii return 0; } if (cod[vecin].second != -cod[nod].second){ if (cod[vecin].second == 1){ x = 1.0 * (tip - cod[nod].first - cod[vecin].first) / 2; found = 1; break; /// ai aflat x } else { x = 1.0 * (cod[vecin].first - tip + cod[nod].first) / 2; found = 1; break; } } } } } if (!found){ mini = 2000000000; poz = -3; for (i = -20 ; i <= 20 ; i++){ sum = 0; for (int k = 0 ; k < taken.size() ; k++){ nod = taken[k]; sum = sum + max(cod[nod].first + cod[nod].second * i , - (cod[nod].first + cod[nod].second * i )); } if (sum < mini){ mini = sum; poz = i; } } x = poz; found = 1; } dq.clear(); dq.push_back(j); f2[j] = 2; sol[j] = x; while (!dq.empty()){ nod = dq.front(); dq.pop_front(); for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; tip = v[nod][i].second; if (f2[vecin] != 2){ dq.push_back(vecin); f2[vecin] = 2; sol[vecin] = tip - sol[nod]; } else { if (sol[vecin] != tip - sol[nod]){ fprintf (fout,"NO"); return 0; } } } } } cout << "YES\n"; for (i = 1 ; i <= n ; i++){ cout << sol[i] << " "; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2760 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Correct | 2 ms | 2636 KB | answer = YES |
6 | Correct | 2 ms | 2636 KB | answer = YES |
7 | Correct | 2 ms | 2636 KB | answer = YES |
8 | Correct | 2 ms | 2636 KB | answer = YES |
9 | Correct | 3 ms | 2740 KB | answer = NO |
10 | Correct | 3 ms | 2636 KB | answer = YES |
11 | Correct | 2 ms | 2636 KB | answer = YES |
12 | Correct | 2 ms | 2636 KB | answer = NO |
13 | Correct | 2 ms | 2636 KB | answer = YES |
14 | Correct | 2 ms | 2636 KB | answer = YES |
15 | Correct | 2 ms | 2636 KB | answer = YES |
16 | Correct | 2 ms | 2636 KB | answer = YES |
17 | Correct | 2 ms | 2636 KB | answer = YES |
18 | Correct | 2 ms | 2636 KB | answer = YES |
19 | Correct | 3 ms | 2636 KB | answer = YES |
20 | Correct | 2 ms | 2636 KB | answer = YES |
21 | Correct | 2 ms | 2636 KB | answer = YES |
22 | Correct | 2 ms | 2636 KB | answer = NO |
23 | Correct | 2 ms | 2636 KB | answer = NO |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2760 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Correct | 2 ms | 2636 KB | answer = YES |
6 | Correct | 2 ms | 2636 KB | answer = YES |
7 | Correct | 2 ms | 2636 KB | answer = YES |
8 | Correct | 2 ms | 2636 KB | answer = YES |
9 | Correct | 3 ms | 2740 KB | answer = NO |
10 | Correct | 3 ms | 2636 KB | answer = YES |
11 | Correct | 2 ms | 2636 KB | answer = YES |
12 | Correct | 2 ms | 2636 KB | answer = NO |
13 | Correct | 2 ms | 2636 KB | answer = YES |
14 | Correct | 2 ms | 2636 KB | answer = YES |
15 | Correct | 2 ms | 2636 KB | answer = YES |
16 | Correct | 2 ms | 2636 KB | answer = YES |
17 | Correct | 2 ms | 2636 KB | answer = YES |
18 | Correct | 2 ms | 2636 KB | answer = YES |
19 | Correct | 3 ms | 2636 KB | answer = YES |
20 | Correct | 2 ms | 2636 KB | answer = YES |
21 | Correct | 2 ms | 2636 KB | answer = YES |
22 | Correct | 2 ms | 2636 KB | answer = NO |
23 | Correct | 2 ms | 2636 KB | answer = NO |
24 | Correct | 2 ms | 2636 KB | answer = YES |
25 | Correct | 2 ms | 2636 KB | answer = YES |
26 | Correct | 2 ms | 2636 KB | answer = YES |
27 | Correct | 2 ms | 2660 KB | answer = YES |
28 | Correct | 2 ms | 2636 KB | answer = YES |
29 | Correct | 3 ms | 2636 KB | answer = YES |
30 | Correct | 2 ms | 2636 KB | answer = NO |
31 | Correct | 2 ms | 2636 KB | answer = YES |
32 | Correct | 2 ms | 2636 KB | answer = YES |
33 | Correct | 3 ms | 2652 KB | answer = YES |
34 | Correct | 2 ms | 2652 KB | answer = YES |
35 | Correct | 2 ms | 2656 KB | answer = YES |
36 | Correct | 2 ms | 2636 KB | answer = YES |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2760 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Correct | 2 ms | 2636 KB | answer = YES |
6 | Correct | 2 ms | 2636 KB | answer = YES |
7 | Correct | 2 ms | 2636 KB | answer = YES |
8 | Correct | 2 ms | 2636 KB | answer = YES |
9 | Correct | 3 ms | 2740 KB | answer = NO |
10 | Correct | 3 ms | 2636 KB | answer = YES |
11 | Correct | 2 ms | 2636 KB | answer = YES |
12 | Correct | 2 ms | 2636 KB | answer = NO |
13 | Correct | 2 ms | 2636 KB | answer = YES |
14 | Correct | 2 ms | 2636 KB | answer = YES |
15 | Correct | 2 ms | 2636 KB | answer = YES |
16 | Correct | 2 ms | 2636 KB | answer = YES |
17 | Correct | 2 ms | 2636 KB | answer = YES |
18 | Correct | 2 ms | 2636 KB | answer = YES |
19 | Correct | 3 ms | 2636 KB | answer = YES |
20 | Correct | 2 ms | 2636 KB | answer = YES |
21 | Correct | 2 ms | 2636 KB | answer = YES |
22 | Correct | 2 ms | 2636 KB | answer = NO |
23 | Correct | 2 ms | 2636 KB | answer = NO |
24 | Correct | 2 ms | 2636 KB | answer = YES |
25 | Correct | 2 ms | 2636 KB | answer = YES |
26 | Correct | 2 ms | 2636 KB | answer = YES |
27 | Correct | 2 ms | 2660 KB | answer = YES |
28 | Correct | 2 ms | 2636 KB | answer = YES |
29 | Correct | 3 ms | 2636 KB | answer = YES |
30 | Correct | 2 ms | 2636 KB | answer = NO |
31 | Correct | 2 ms | 2636 KB | answer = YES |
32 | Correct | 2 ms | 2636 KB | answer = YES |
33 | Correct | 3 ms | 2652 KB | answer = YES |
34 | Correct | 2 ms | 2652 KB | answer = YES |
35 | Correct | 2 ms | 2656 KB | answer = YES |
36 | Correct | 2 ms | 2636 KB | answer = YES |
37 | Correct | 2 ms | 2636 KB | answer = YES |
38 | Correct | 2 ms | 2636 KB | answer = YES |
39 | Correct | 3 ms | 2636 KB | answer = YES |
40 | Correct | 3 ms | 2636 KB | answer = YES |
41 | Correct | 3 ms | 2636 KB | answer = NO |
42 | Correct | 3 ms | 2636 KB | answer = YES |
43 | Correct | 3 ms | 2636 KB | answer = YES |
44 | Correct | 4 ms | 2636 KB | answer = YES |
45 | Correct | 3 ms | 2636 KB | answer = YES |
46 | Correct | 3 ms | 2660 KB | answer = YES |
47 | Correct | 3 ms | 2636 KB | answer = YES |
48 | Correct | 3 ms | 2636 KB | answer = YES |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2760 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Correct | 2 ms | 2636 KB | answer = YES |
6 | Correct | 2 ms | 2636 KB | answer = YES |
7 | Correct | 2 ms | 2636 KB | answer = YES |
8 | Correct | 2 ms | 2636 KB | answer = YES |
9 | Correct | 3 ms | 2740 KB | answer = NO |
10 | Correct | 3 ms | 2636 KB | answer = YES |
11 | Correct | 2 ms | 2636 KB | answer = YES |
12 | Correct | 2 ms | 2636 KB | answer = NO |
13 | Correct | 2 ms | 2636 KB | answer = YES |
14 | Correct | 2 ms | 2636 KB | answer = YES |
15 | Correct | 2 ms | 2636 KB | answer = YES |
16 | Correct | 2 ms | 2636 KB | answer = YES |
17 | Correct | 2 ms | 2636 KB | answer = YES |
18 | Correct | 2 ms | 2636 KB | answer = YES |
19 | Correct | 3 ms | 2636 KB | answer = YES |
20 | Correct | 2 ms | 2636 KB | answer = YES |
21 | Correct | 2 ms | 2636 KB | answer = YES |
22 | Correct | 2 ms | 2636 KB | answer = NO |
23 | Correct | 2 ms | 2636 KB | answer = NO |
24 | Correct | 2 ms | 2636 KB | answer = YES |
25 | Correct | 2 ms | 2636 KB | answer = YES |
26 | Correct | 2 ms | 2636 KB | answer = YES |
27 | Correct | 2 ms | 2660 KB | answer = YES |
28 | Correct | 2 ms | 2636 KB | answer = YES |
29 | Correct | 3 ms | 2636 KB | answer = YES |
30 | Correct | 2 ms | 2636 KB | answer = NO |
31 | Correct | 2 ms | 2636 KB | answer = YES |
32 | Correct | 2 ms | 2636 KB | answer = YES |
33 | Correct | 3 ms | 2652 KB | answer = YES |
34 | Correct | 2 ms | 2652 KB | answer = YES |
35 | Correct | 2 ms | 2656 KB | answer = YES |
36 | Correct | 2 ms | 2636 KB | answer = YES |
37 | Correct | 2 ms | 2636 KB | answer = YES |
38 | Correct | 2 ms | 2636 KB | answer = YES |
39 | Correct | 3 ms | 2636 KB | answer = YES |
40 | Correct | 3 ms | 2636 KB | answer = YES |
41 | Correct | 3 ms | 2636 KB | answer = NO |
42 | Correct | 3 ms | 2636 KB | answer = YES |
43 | Correct | 3 ms | 2636 KB | answer = YES |
44 | Correct | 4 ms | 2636 KB | answer = YES |
45 | Correct | 3 ms | 2636 KB | answer = YES |
46 | Correct | 3 ms | 2660 KB | answer = YES |
47 | Correct | 3 ms | 2636 KB | answer = YES |
48 | Correct | 3 ms | 2636 KB | answer = YES |
49 | Correct | 14 ms | 3452 KB | answer = YES |
50 | Correct | 15 ms | 3308 KB | answer = YES |
51 | Correct | 13 ms | 3436 KB | answer = YES |
52 | Correct | 6 ms | 3192 KB | answer = NO |
53 | Correct | 3 ms | 2684 KB | answer = YES |
54 | Correct | 6 ms | 2764 KB | answer = YES |
55 | Correct | 7 ms | 3020 KB | answer = YES |
56 | Correct | 16 ms | 3404 KB | answer = YES |
57 | Correct | 13 ms | 3300 KB | answer = YES |
58 | Correct | 11 ms | 3328 KB | answer = YES |
59 | Correct | 11 ms | 3296 KB | answer = YES |
60 | Correct | 13 ms | 3444 KB | answer = YES |
61 | Correct | 7 ms | 3020 KB | answer = YES |
62 | Correct | 76 ms | 9760 KB | answer = NO |
63 | Correct | 85 ms | 9700 KB | answer = YES |
64 | Correct | 77 ms | 9796 KB | answer = NO |
65 | Correct | 79 ms | 9744 KB | answer = YES |
66 | Correct | 4 ms | 2764 KB | answer = YES |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2760 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Correct | 2 ms | 2636 KB | answer = YES |
6 | Correct | 2 ms | 2636 KB | answer = YES |
7 | Correct | 2 ms | 2636 KB | answer = YES |
8 | Correct | 2 ms | 2636 KB | answer = YES |
9 | Correct | 3 ms | 2740 KB | answer = NO |
10 | Correct | 3 ms | 2636 KB | answer = YES |
11 | Correct | 2 ms | 2636 KB | answer = YES |
12 | Correct | 2 ms | 2636 KB | answer = NO |
13 | Correct | 2 ms | 2636 KB | answer = YES |
14 | Correct | 2 ms | 2636 KB | answer = YES |
15 | Correct | 2 ms | 2636 KB | answer = YES |
16 | Correct | 2 ms | 2636 KB | answer = YES |
17 | Correct | 2 ms | 2636 KB | answer = YES |
18 | Correct | 2 ms | 2636 KB | answer = YES |
19 | Correct | 3 ms | 2636 KB | answer = YES |
20 | Correct | 2 ms | 2636 KB | answer = YES |
21 | Correct | 2 ms | 2636 KB | answer = YES |
22 | Correct | 2 ms | 2636 KB | answer = NO |
23 | Correct | 2 ms | 2636 KB | answer = NO |
24 | Correct | 2 ms | 2636 KB | answer = YES |
25 | Correct | 2 ms | 2636 KB | answer = YES |
26 | Correct | 2 ms | 2636 KB | answer = YES |
27 | Correct | 2 ms | 2660 KB | answer = YES |
28 | Correct | 2 ms | 2636 KB | answer = YES |
29 | Correct | 3 ms | 2636 KB | answer = YES |
30 | Correct | 2 ms | 2636 KB | answer = NO |
31 | Correct | 2 ms | 2636 KB | answer = YES |
32 | Correct | 2 ms | 2636 KB | answer = YES |
33 | Correct | 3 ms | 2652 KB | answer = YES |
34 | Correct | 2 ms | 2652 KB | answer = YES |
35 | Correct | 2 ms | 2656 KB | answer = YES |
36 | Correct | 2 ms | 2636 KB | answer = YES |
37 | Correct | 2 ms | 2636 KB | answer = YES |
38 | Correct | 2 ms | 2636 KB | answer = YES |
39 | Correct | 3 ms | 2636 KB | answer = YES |
40 | Correct | 3 ms | 2636 KB | answer = YES |
41 | Correct | 3 ms | 2636 KB | answer = NO |
42 | Correct | 3 ms | 2636 KB | answer = YES |
43 | Correct | 3 ms | 2636 KB | answer = YES |
44 | Correct | 4 ms | 2636 KB | answer = YES |
45 | Correct | 3 ms | 2636 KB | answer = YES |
46 | Correct | 3 ms | 2660 KB | answer = YES |
47 | Correct | 3 ms | 2636 KB | answer = YES |
48 | Correct | 3 ms | 2636 KB | answer = YES |
49 | Correct | 14 ms | 3452 KB | answer = YES |
50 | Correct | 15 ms | 3308 KB | answer = YES |
51 | Correct | 13 ms | 3436 KB | answer = YES |
52 | Correct | 6 ms | 3192 KB | answer = NO |
53 | Correct | 3 ms | 2684 KB | answer = YES |
54 | Correct | 6 ms | 2764 KB | answer = YES |
55 | Correct | 7 ms | 3020 KB | answer = YES |
56 | Correct | 16 ms | 3404 KB | answer = YES |
57 | Correct | 13 ms | 3300 KB | answer = YES |
58 | Correct | 11 ms | 3328 KB | answer = YES |
59 | Correct | 11 ms | 3296 KB | answer = YES |
60 | Correct | 13 ms | 3444 KB | answer = YES |
61 | Correct | 7 ms | 3020 KB | answer = YES |
62 | Correct | 76 ms | 9760 KB | answer = NO |
63 | Correct | 85 ms | 9700 KB | answer = YES |
64 | Correct | 77 ms | 9796 KB | answer = NO |
65 | Correct | 79 ms | 9744 KB | answer = YES |
66 | Correct | 4 ms | 2764 KB | answer = YES |
67 | Incorrect | 103 ms | 10280 KB | participant answer is larger than the answer of jury |
68 | Halted | 0 ms | 0 KB | - |