oj.uz

Submission #974001

# Submission time Handle Problem Language Result Execution time Memory
974001 2024-05-02T14:48:09 Z Onur_Ilgaz Graph (BOI20_graph) C++17
100 / 100
 123 ms 28768 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 100001;
vector <pair<int, int> > adj[N];
int root[N], sign[N];
bitset <N> cons;
double val[N], add[N];
vector <double> idk;

double calc(int node) {
	return val[node] + add[root[node]] * sign[node];
}

void dfs1(int node, int comp, bool sgn) { // constant olabilenleri constant yap
	sign[node] = sgn ? 1 : -1;
	root[node] = comp;
	idk.push_back(val[node] * sign[node]);
	for(auto [to, w]:adj[node]) {
		if(!root[to]) {
			val[to] = w - val[node];
			dfs1(to, comp, !sgn);
		}
		else {
			if(cons[root[node]]) {
				if(calc(node) + calc(to) != w) {
					cout << "NO";
					exit(0);
				}
			}
			else {
				if(sign[node] == sign[to]) {
					cons[root[node]] = 1;
					double diff = w - (val[node] + val[to]);
					add[root[node]] = diff / 2 * sign[node];
				}
				else {
					if(val[node] + val[to] != w) {
						cout << "NO";
						exit(0);
					}
				}
			}
		}
	}
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	for(int i = 1; i <= n; i++) {
		if(root[i]) continue;
		idk.clear();
		dfs1(i, i, 1);
		// if inconsistent, then do some value adjustments
		if(!cons[i]) {
			sort(idk.begin(), idk.end());
			double midi = idk[idk.size() / 2];
			add[i] = -midi;
			//cout << midi << "\n";
		}
	}
	cout << "YES\n";

	for(int i = 1; i <= n; i++) {
		cout << calc(i) << " ";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB answer = YES
2 Correct 1 ms 3676 KB answer = YES
3 Correct 1 ms 3720 KB answer = YES
4 Correct 1 ms 3676 KB answer = NO
5 Correct 1 ms 3676 KB answer = YES
6 Correct 1 ms 3676 KB answer = YES
7 Correct 1 ms 3676 KB answer = YES
8 Correct 1 ms 3672 KB answer = YES
9 Correct 1 ms 3672 KB answer = NO
10 Correct 1 ms 3676 KB answer = YES
11 Correct 1 ms 3676 KB answer = YES
12 Correct 1 ms 3676 KB answer = NO
13 Correct 1 ms 3676 KB answer = YES
14 Correct 1 ms 3716 KB answer = YES
15 Correct 1 ms 3592 KB answer = YES
16 Correct 1 ms 3676 KB answer = YES
17 Correct 1 ms 3676 KB answer = YES
18 Correct 1 ms 3672 KB answer = YES
19 Correct 1 ms 3676 KB answer = YES
20 Correct 1 ms 3720 KB answer = YES
21 Correct 1 ms 3676 KB answer = YES
22 Correct 1 ms 3716 KB answer = NO
23 Correct 1 ms 3676 KB answer = NO
24 Correct 1 ms 3676 KB answer = YES
25 Correct 1 ms 3676 KB answer = YES
26 Correct 1 ms 3676 KB answer = YES
27 Correct 1 ms 3676 KB answer = YES
28 Correct 1 ms 3676 KB answer = YES
29 Correct 1 ms 3676 KB answer = YES
30 Correct 1 ms 3672 KB answer = NO
31 Correct 2 ms 3932 KB answer = YES
32 Correct 1 ms 3676 KB answer = YES
33 Correct 1 ms 3716 KB answer = YES
34 Correct 2 ms 3672 KB answer = YES
35 Correct 1 ms 3676 KB answer = YES
36 Correct 1 ms 3676 KB answer = YES
37 Correct 1 ms 3676 KB answer = YES
38 Correct 1 ms 3676 KB answer = YES
39 Correct 2 ms 3676 KB answer = YES
40 Correct 2 ms 3676 KB answer = YES
41 Correct 2 ms 3676 KB answer = NO
42 Correct 2 ms 3676 KB answer = YES
43 Correct 2 ms 3932 KB answer = YES
44 Correct 2 ms 3676 KB answer = YES
45 Correct 2 ms 3676 KB answer = YES
46 Correct 2 ms 3676 KB answer = YES
47 Correct 2 ms 3672 KB answer = YES
48 Correct 2 ms 3676 KB answer = YES
49 Correct 8 ms 4696 KB answer = YES
50 Correct 8 ms 5212 KB answer = YES
51 Correct 7 ms 5212 KB answer = YES
52 Correct 4 ms 4440 KB answer = NO
53 Correct 2 ms 3676 KB answer = YES
54 Correct 3 ms 3932 KB answer = YES
55 Correct 4 ms 4188 KB answer = YES
56 Correct 7 ms 4700 KB answer = YES
57 Correct 7 ms 4444 KB answer = YES
58 Correct 7 ms 4440 KB answer = YES
59 Correct 7 ms 4440 KB answer = YES
60 Correct 7 ms 4444 KB answer = YES
61 Correct 4 ms 4192 KB answer = YES
62 Correct 44 ms 14932 KB answer = NO
63 Correct 48 ms 15696 KB answer = YES
64 Correct 46 ms 15696 KB answer = NO
65 Correct 48 ms 15696 KB answer = YES
66 Correct 3 ms 3672 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB answer = YES
2 Correct 1 ms 3676 KB answer = YES
3 Correct 1 ms 3720 KB answer = YES
4 Correct 1 ms 3676 KB answer = NO
5 Correct 1 ms 3676 KB answer = YES
6 Correct 1 ms 3676 KB answer = YES
7 Correct 1 ms 3676 KB answer = YES
8 Correct 1 ms 3672 KB answer = YES
9 Correct 1 ms 3672 KB answer = NO
10 Correct 1 ms 3676 KB answer = YES
11 Correct 1 ms 3676 KB answer = YES
12 Correct 1 ms 3676 KB answer = NO
13 Correct 1 ms 3676 KB answer = YES
14 Correct 1 ms 3716 KB answer = YES
15 Correct 1 ms 3592 KB answer = YES
16 Correct 1 ms 3676 KB answer = YES
17 Correct 1 ms 3676 KB answer = YES
18 Correct 1 ms 3672 KB answer = YES
19 Correct 1 ms 3676 KB answer = YES
20 Correct 1 ms 3720 KB answer = YES
21 Correct 1 ms 3676 KB answer = YES
22 Correct 1 ms 3716 KB answer = NO
23 Correct 1 ms 3676 KB answer = NO
24 Correct 1 ms 3676 KB answer = YES
25 Correct 1 ms 3676 KB answer = YES
26 Correct 1 ms 3676 KB answer = YES
27 Correct 1 ms 3676 KB answer = YES
28 Correct 1 ms 3676 KB answer = YES
29 Correct 1 ms 3676 KB answer = YES
30 Correct 1 ms 3672 KB answer = NO
31 Correct 2 ms 3932 KB answer = YES
32 Correct 1 ms 3676 KB answer = YES
33 Correct 1 ms 3716 KB answer = YES
34 Correct 2 ms 3672 KB answer = YES
35 Correct 1 ms 3676 KB answer = YES
36 Correct 1 ms 3676 KB answer = YES
37 Correct 1 ms 3676 KB answer = YES
38 Correct 1 ms 3676 KB answer = YES
39 Correct 2 ms 3676 KB answer = YES
40 Correct 2 ms 3676 KB answer = YES
41 Correct 2 ms 3676 KB answer = NO
42 Correct 2 ms 3676 KB answer = YES
43 Correct 2 ms 3932 KB answer = YES
44 Correct 2 ms 3676 KB answer = YES
45 Correct 2 ms 3676 KB answer = YES
46 Correct 2 ms 3676 KB answer = YES
47 Correct 2 ms 3672 KB answer = YES
48 Correct 2 ms 3676 KB answer = YES
49 Correct 8 ms 4696 KB answer = YES
50 Correct 8 ms 5212 KB answer = YES
51 Correct 7 ms 5212 KB answer = YES
52 Correct 4 ms 4440 KB answer = NO
53 Correct 2 ms 3676 KB answer = YES
54 Correct 3 ms 3932 KB answer = YES
55 Correct 4 ms 4188 KB answer = YES
56 Correct 7 ms 4700 KB answer = YES
57 Correct 7 ms 4444 KB answer = YES
58 Correct 7 ms 4440 KB answer = YES
59 Correct 7 ms 4440 KB answer = YES
60 Correct 7 ms 4444 KB answer = YES
61 Correct 4 ms 4192 KB answer = YES
62 Correct 44 ms 14932 KB answer = NO
63 Correct 48 ms 15696 KB answer = YES
64 Correct 46 ms 15696 KB answer = NO
65 Correct 48 ms 15696 KB answer = YES
66 Correct 3 ms 3672 KB answer = YES
67 Correct 77 ms 21700 KB answer = YES
68 Correct 70 ms 21492 KB answer = YES
69 Correct 65 ms 21636 KB answer = YES
70 Correct 95 ms 28768 KB answer = YES
71 Correct 67 ms 21876 KB answer = YES
72 Correct 67 ms 12752 KB answer = YES
73 Correct 64 ms 12760 KB answer = YES
74 Correct 45 ms 14292 KB answer = YES
75 Correct 24 ms 11216 KB answer = NO
76 Correct 9 ms 4696 KB answer = YES
77 Correct 18 ms 6076 KB answer = YES
78 Correct 28 ms 7636 KB answer = YES
79 Correct 62 ms 11472 KB answer = YES
80 Correct 47 ms 14284 KB answer = YES
81 Correct 34 ms 16844 KB answer = NO
82 Correct 84 ms 21212 KB answer = YES
83 Correct 88 ms 22300 KB answer = YES
84 Correct 88 ms 22204 KB answer = YES
85 Correct 70 ms 21688 KB answer = YES
86 Correct 77 ms 21960 KB answer = YES
87 Correct 36 ms 14552 KB answer = NO
88 Correct 88 ms 16580 KB answer = YES
89 Correct 67 ms 12112 KB answer = YES
90 Correct 69 ms 12112 KB answer = YES
91 Correct 69 ms 12584 KB answer = YES
92 Correct 33 ms 8428 KB answer = YES
93 Correct 48 ms 8408 KB answer = YES
94 Correct 45 ms 21944 KB answer = NO
95 Correct 31 ms 11760 KB answer = NO
96 Correct 123 ms 25448 KB answer = YES
97 Correct 31 ms 21512 KB answer = NO