oj.uz

Submission #718791

# Submission time Handle Problem Language Result Execution time Memory
718791 2023-04-04T20:22:50 Z Charizard2021 Graph (BOI20_graph) C++17
100 / 100
 258 ms 13912 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
bool visited[N];
int sign[N];
int arr[N];
int val[N];
int val2[N];
int answer[N];
vector<pair<int, int> > adj[N];
int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		c *= 2;
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
	}
	for(int i = 1; i <= n; i++) {
		if(!visited[i]) {
			visited[i] = true;
            int idx = 0;
			sign[i] = 1;
			val[i] = 0;
			arr[idx] = i;
            idx++;
			bool bipartite = true;
			double x2;
            queue<int> q;
            q.push(i);
			while(!q.empty()) {
				int u = q.front();
                q.pop();
                for(pair<int, int> x : adj[u]){
                    int v = x.first;
                    int weight = x.second;
                    if(!visited[v]){
                        visited[v] = true;
                        sign[v] = -sign[u];
                        val[v] = weight - val[u];
                        arr[idx] = v;
                        idx++;
                        q.push(v);
                    }
                    else if(sign[v] == sign[u]){
                        bipartite = false;
                        x2 = (sign[v]) * (weight - val[v] - val[u])/2;
                    }
                }
			}
            if(bipartite){
                for(int j = 0; j < idx; j++){
                    int u = arr[j];
                    val2[j] = (-sign[u]) * val[u];
                }
                sort(val2, val2 + idx);
                x2 = val2[idx/2];
            }
            for(int j = 0; j < idx; j++){
                int u = arr[j];
                answer[u] = val[u] + sign[u] * x2;
            }
            for(int j = 0; j < idx; j++){
                int u = arr[j];
                for(pair<int, int> x : adj[u]){
                    int v = x.first;
                    if(answer[v] + answer[u] != x.second){
                        cout << "NO\n";
                        return 0;
                    }
                }
            }
		}
	}
    cout << "YES\n";
	for(int u = 1; u <= n; u++) {
        cout << 0.5 * answer[u] << " ";
	}
    cout << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2660 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2772 KB answer = YES
11 Correct 2 ms 2660 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2660 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2660 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2660 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2652 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2660 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2772 KB answer = YES
11 Correct 2 ms 2660 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2660 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2660 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2660 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2652 KB answer = NO
24 Correct 2 ms 2644 KB answer = YES
25 Correct 2 ms 2644 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2656 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2660 KB answer = YES
32 Correct 2 ms 2660 KB answer = YES
33 Correct 2 ms 2660 KB answer = YES
34 Correct 2 ms 2656 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2660 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2772 KB answer = YES
11 Correct 2 ms 2660 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2660 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2660 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2660 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2652 KB answer = NO
24 Correct 2 ms 2644 KB answer = YES
25 Correct 2 ms 2644 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2656 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2660 KB answer = YES
32 Correct 2 ms 2660 KB answer = YES
33 Correct 2 ms 2660 KB answer = YES
34 Correct 2 ms 2656 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 3 ms 2668 KB answer = YES
41 Correct 2 ms 2644 KB answer = NO
42 Correct 3 ms 2644 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 3 ms 2644 KB answer = YES
45 Correct 3 ms 2704 KB answer = YES
46 Correct 3 ms 2664 KB answer = YES
47 Correct 4 ms 2720 KB answer = YES
48 Correct 4 ms 2644 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2660 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2772 KB answer = YES
11 Correct 2 ms 2660 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2660 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2660 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2660 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2652 KB answer = NO
24 Correct 2 ms 2644 KB answer = YES
25 Correct 2 ms 2644 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2656 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2660 KB answer = YES
32 Correct 2 ms 2660 KB answer = YES
33 Correct 2 ms 2660 KB answer = YES
34 Correct 2 ms 2656 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 3 ms 2668 KB answer = YES
41 Correct 2 ms 2644 KB answer = NO
42 Correct 3 ms 2644 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 3 ms 2644 KB answer = YES
45 Correct 3 ms 2704 KB answer = YES
46 Correct 3 ms 2664 KB answer = YES
47 Correct 4 ms 2720 KB answer = YES
48 Correct 4 ms 2644 KB answer = YES
49 Correct 13 ms 3284 KB answer = YES
50 Correct 13 ms 3284 KB answer = YES
51 Correct 13 ms 3324 KB answer = YES
52 Correct 10 ms 3316 KB answer = NO
53 Correct 3 ms 2668 KB answer = YES
54 Correct 4 ms 2852 KB answer = YES
55 Correct 10 ms 3028 KB answer = YES
56 Correct 14 ms 3284 KB answer = YES
57 Correct 12 ms 3284 KB answer = YES
58 Correct 12 ms 3188 KB answer = YES
59 Correct 17 ms 3284 KB answer = YES
60 Correct 14 ms 3360 KB answer = YES
61 Correct 7 ms 2900 KB answer = YES
62 Correct 136 ms 9744 KB answer = NO
63 Correct 136 ms 9644 KB answer = YES
64 Correct 143 ms 9740 KB answer = NO
65 Correct 136 ms 9640 KB answer = YES
66 Correct 6 ms 2772 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2660 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2772 KB answer = YES
11 Correct 2 ms 2660 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2660 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2660 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2660 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 2 ms 2652 KB answer = NO
24 Correct 2 ms 2644 KB answer = YES
25 Correct 2 ms 2644 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2656 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2660 KB answer = YES
32 Correct 2 ms 2660 KB answer = YES
33 Correct 2 ms 2660 KB answer = YES
34 Correct 2 ms 2656 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 3 ms 2668 KB answer = YES
41 Correct 2 ms 2644 KB answer = NO
42 Correct 3 ms 2644 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 3 ms 2644 KB answer = YES
45 Correct 3 ms 2704 KB answer = YES
46 Correct 3 ms 2664 KB answer = YES
47 Correct 4 ms 2720 KB answer = YES
48 Correct 4 ms 2644 KB answer = YES
49 Correct 13 ms 3284 KB answer = YES
50 Correct 13 ms 3284 KB answer = YES
51 Correct 13 ms 3324 KB answer = YES
52 Correct 10 ms 3316 KB answer = NO
53 Correct 3 ms 2668 KB answer = YES
54 Correct 4 ms 2852 KB answer = YES
55 Correct 10 ms 3028 KB answer = YES
56 Correct 14 ms 3284 KB answer = YES
57 Correct 12 ms 3284 KB answer = YES
58 Correct 12 ms 3188 KB answer = YES
59 Correct 17 ms 3284 KB answer = YES
60 Correct 14 ms 3360 KB answer = YES
61 Correct 7 ms 2900 KB answer = YES
62 Correct 136 ms 9744 KB answer = NO
63 Correct 136 ms 9644 KB answer = YES
64 Correct 143 ms 9740 KB answer = NO
65 Correct 136 ms 9640 KB answer = YES
66 Correct 6 ms 2772 KB answer = YES
67 Correct 121 ms 9424 KB answer = YES
68 Correct 123 ms 9332 KB answer = YES
69 Correct 131 ms 8972 KB answer = YES
70 Correct 182 ms 13388 KB answer = YES
71 Correct 115 ms 9132 KB answer = YES
72 Correct 145 ms 9964 KB answer = YES
73 Correct 149 ms 9664 KB answer = YES
74 Correct 89 ms 6812 KB answer = YES
75 Correct 53 ms 6860 KB answer = NO
76 Correct 15 ms 3548 KB answer = YES
77 Correct 32 ms 4456 KB answer = YES
78 Correct 60 ms 5788 KB answer = YES
79 Correct 122 ms 8936 KB answer = YES
80 Correct 82 ms 7068 KB answer = YES
81 Correct 94 ms 8684 KB answer = NO
82 Correct 149 ms 9324 KB answer = YES
83 Correct 147 ms 9140 KB answer = YES
84 Correct 177 ms 9472 KB answer = YES
85 Correct 119 ms 9536 KB answer = YES
86 Correct 125 ms 9108 KB answer = YES
87 Correct 107 ms 8524 KB answer = NO
88 Correct 162 ms 8984 KB answer = YES
89 Correct 143 ms 8800 KB answer = YES
90 Correct 121 ms 8704 KB answer = YES
91 Correct 138 ms 8656 KB answer = YES
92 Correct 78 ms 6256 KB answer = YES
93 Correct 65 ms 6112 KB answer = YES
94 Correct 109 ms 9096 KB answer = NO
95 Correct 82 ms 8396 KB answer = NO
96 Correct 258 ms 13912 KB answer = YES
97 Correct 82 ms 9272 KB answer = NO