oj.uz

Submission #447292

# Submission time Handle Problem Language Result Execution time Memory
447292 2021-07-25T20:43:08 Z jhnah917 Graph (BOI20_graph) C++14
100 / 100
 207 ms 30956 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using ll = long long;
using ld = long double;
using PLL = pair<ll, ll>;
using PDD = pair<ld, ld>;
inline void DIE(){ cout << "NO"; exit(0); }

int N, M;
vector<PLL> G[101010];
PDD A[101010];
bool C[101010];
vector<double> Fix;
vector<ll> Can, Vis;
double R[101010];

void DFS(int v, int mul, ll add){
    if(!C[v]) A[v] = {mul, add};
    else if(A[v].x == mul && A[v].y == add) return;
    else if(A[v].x == mul && A[v].y != add) DIE();
    else{
        Fix.push_back(1.0 * (A[v].y - add) / (mul - A[v].x));
        return;
    }
    Vis.push_back(v); C[v] = true;
    if(mul == 1) Can.push_back(-add);
    else Can.push_back(add);
    for(auto [i,w] : G[v]) DFS(i, -mul, w-add);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++){
        int s, e, x; cin >> s >> e >> x;
        G[s].emplace_back(e, x);
        G[e].emplace_back(s, x);
    }
    for(int i=1; i<=N; i++){
        if(C[i]) continue;
        Fix.clear(); Can.clear(); Vis.clear();
        DFS(i, 1, 0);
        sort(Can.begin(), Can.end());
        sort(Fix.begin(), Fix.end());
        Fix.erase(unique(Fix.begin(), Fix.end()), Fix.end());
        if(Fix.size() > 1) DIE();
        double X = Fix.size() == 1 ? Fix[0] : Can[Can.size()/2];
        for(auto j : Vis) R[j] = A[j].x * X + A[j].y;
    }
    cout << "YES\n";
    for(int i=1; i<=N; i++) cout << R[i] << " ";
}

Compilation message

Graph.cpp: In function 'void DFS(int, int, ll)':
Graph.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [i,w] : G[v]) DFS(i, -mul, w-add);
      |              ^

Subtask #1
5.0 / 5.0

# 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 2636 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 2 ms 2636 KB answer = NO
10 Correct 2 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 2 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 2704 KB answer = NO

Subtask #2
12.0 / 12.0

# 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 2636 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 2 ms 2636 KB answer = NO
10 Correct 2 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 2 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 2704 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 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2696 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 2 ms 2700 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2700 KB answer = YES

Subtask #3
17.0 / 17.0

# 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 2636 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 2 ms 2636 KB answer = NO
10 Correct 2 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 2 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 2704 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 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2696 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 2 ms 2700 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2700 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 2 ms 2764 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2764 KB answer = NO
42 Correct 3 ms 2764 KB answer = YES
43 Correct 3 ms 2764 KB answer = YES
44 Correct 4 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 2 ms 2764 KB answer = YES
47 Correct 3 ms 2888 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES

Subtask #4
24.0 / 24.0

# 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 2636 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 2 ms 2636 KB answer = NO
10 Correct 2 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 2 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 2704 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 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2696 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 2 ms 2700 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2700 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 2 ms 2764 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2764 KB answer = NO
42 Correct 3 ms 2764 KB answer = YES
43 Correct 3 ms 2764 KB answer = YES
44 Correct 4 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 2 ms 2764 KB answer = YES
47 Correct 3 ms 2888 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES
49 Correct 12 ms 4044 KB answer = YES
50 Correct 12 ms 4380 KB answer = YES
51 Correct 12 ms 4348 KB answer = YES
52 Correct 6 ms 3608 KB answer = NO
53 Correct 3 ms 2764 KB answer = YES
54 Correct 4 ms 3020 KB answer = YES
55 Correct 7 ms 3404 KB answer = YES
56 Correct 11 ms 4044 KB answer = YES
57 Correct 11 ms 3788 KB answer = YES
58 Correct 10 ms 3788 KB answer = YES
59 Correct 11 ms 3788 KB answer = YES
60 Correct 12 ms 3988 KB answer = YES
61 Correct 7 ms 3356 KB answer = YES
62 Correct 74 ms 14344 KB answer = NO
63 Correct 88 ms 17244 KB answer = YES
64 Correct 85 ms 17276 KB answer = NO
65 Correct 88 ms 17244 KB answer = YES
66 Correct 4 ms 2892 KB answer = YES

Subtask #5
42.0 / 42.0

# 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 2636 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 2 ms 2636 KB answer = NO
10 Correct 2 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 2 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 2704 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 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2696 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 2 ms 2700 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2700 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 2 ms 2764 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2764 KB answer = NO
42 Correct 3 ms 2764 KB answer = YES
43 Correct 3 ms 2764 KB answer = YES
44 Correct 4 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 2 ms 2764 KB answer = YES
47 Correct 3 ms 2888 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES
49 Correct 12 ms 4044 KB answer = YES
50 Correct 12 ms 4380 KB answer = YES
51 Correct 12 ms 4348 KB answer = YES
52 Correct 6 ms 3608 KB answer = NO
53 Correct 3 ms 2764 KB answer = YES
54 Correct 4 ms 3020 KB answer = YES
55 Correct 7 ms 3404 KB answer = YES
56 Correct 11 ms 4044 KB answer = YES
57 Correct 11 ms 3788 KB answer = YES
58 Correct 10 ms 3788 KB answer = YES
59 Correct 11 ms 3788 KB answer = YES
60 Correct 12 ms 3988 KB answer = YES
61 Correct 7 ms 3356 KB answer = YES
62 Correct 74 ms 14344 KB answer = NO
63 Correct 88 ms 17244 KB answer = YES
64 Correct 85 ms 17276 KB answer = NO
65 Correct 88 ms 17244 KB answer = YES
66 Correct 4 ms 2892 KB answer = YES
67 Correct 98 ms 22584 KB answer = YES
68 Correct 96 ms 22396 KB answer = YES
69 Correct 94 ms 22456 KB answer = YES
70 Correct 157 ms 30956 KB answer = YES
71 Correct 107 ms 22580 KB answer = YES
72 Correct 121 ms 15200 KB answer = YES
73 Correct 131 ms 15216 KB answer = YES
74 Correct 71 ms 14648 KB answer = YES
75 Correct 32 ms 11324 KB answer = NO
76 Correct 14 ms 4300 KB answer = YES
77 Correct 27 ms 5752 KB answer = YES
78 Correct 53 ms 8080 KB answer = YES
79 Correct 96 ms 13296 KB answer = YES
80 Correct 80 ms 14680 KB answer = YES
81 Correct 60 ms 17512 KB answer = NO
82 Correct 118 ms 22180 KB answer = YES
83 Correct 138 ms 23192 KB answer = YES
84 Correct 129 ms 23172 KB answer = YES
85 Correct 99 ms 22588 KB answer = YES
86 Correct 121 ms 22548 KB answer = YES
87 Correct 67 ms 16172 KB answer = NO
88 Correct 160 ms 17964 KB answer = YES
89 Correct 110 ms 13008 KB answer = YES
90 Correct 104 ms 12940 KB answer = YES
91 Correct 116 ms 13508 KB answer = YES
92 Correct 55 ms 9056 KB answer = YES
93 Correct 53 ms 8936 KB answer = YES
94 Correct 77 ms 22088 KB answer = NO
95 Correct 53 ms 13184 KB answer = NO
96 Correct 207 ms 27208 KB answer = YES
97 Correct 56 ms 21488 KB answer = NO