oj.uz

Submission #751587

# Submission time Handle Problem Language Result Execution time Memory
751587 2023-05-31T19:46:37 Z javotaz Graph (BOI20_graph) C++17
100 / 100
 194 ms 20972 KB 
// be nam khodavand jano kherad     kazin bartar andishe bar nagzarad
#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 12;
int n, m, bakhsh[N], omgh[N];
double x[N], check;
bool mrk[N];
vector<pair<int, int> > g[N], xs;
 
void output() {
	cout << "YES\n";
	for (int i = 1; i <= n; i++)
		cout << x[i] << ' ';
}
 
void wrong_output() {
	cout << "NO\n";
	exit(0);
}
 
void check_ans(int a) {
	for (auto i: g[a]) {
		int v = i.first;
		int dis = i.second;
		if (mrk[v]) {
			if (dis - x[a] != x[v])
				wrong_output();
		}
		else {
			mrk[v] = true;
			x[v] = dis - x[a];
			check_ans(v);
		}
	}
}
 
void dfs(int u) {
	for (auto i: g[u]) {
		int v = i.first;
		if (omgh[v] == omgh[u]) {
			check = (x[v] * -1 * omgh[v] + ((i.second - x[u]) * omgh[u])) / 2.0; 
			return;
		}
		if (!omgh[v]) {
			omgh[v] = omgh[u] * -1;
			x[v] = i.second - x[u];  
			dfs(v);
		}
	}
}
 
void dfs_fill_x(int a) {
	for (auto i: g[a]) {
		int u = i.first;
		omgh[u] = omgh[a] * -1;
		int tmp = (i.second - omgh[a] * x[a]) * omgh[u];
		if (mrk[u]) {
			if (x[u] != tmp)
				wrong_output();
		}
		else {
			x[u] = tmp;
			xs.push_back({tmp, u});
			mrk[u] = true;
			dfs_fill_x(u);
		}
	}
}
 
void minimize_output() {
	sort(xs.begin(), xs.end());
	int tmp = xs.size();
	tmp /= 2;
	int r = xs[tmp].first;
	for (auto i: xs) 
		x[i.second] = (i.first - r) * omgh[i.second];
}
 
bool do_bakhshi(int u) {
	bool res = true;
	for (auto i: g[u]) {
		int v = i.first;
		if (bakhsh[v] == bakhsh[u])
			return false;
		if (!bakhsh[v]) {
			bakhsh[v] = (bakhsh[u] == 1)? 2 : 1;
			res &= do_bakhshi(v);
		}
	}
	return res;
}
 
void solve() {
	for (int i = 1; i <= n; i++) {
		if (!mrk[i]) {
			xs.clear();
			xs.push_back({0, i});
			check = 0;
			bakhsh[i] = 1;
			omgh[i] = 1;
			mrk[i] = true;
			if (do_bakhshi(i)) dfs_fill_x(i), minimize_output();
			else {
				dfs(i);
				x[i] = check;
				check_ans(i);
			}
		}
	}
}
 
void input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, color;
		cin >> u >> v >> color;
		g[u].push_back({v, color});
		g[v].push_back({u, color});
	}
}
 
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input(), solve(), output();
}
 
// migan garme bazar kheila

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2676 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2676 KB answer = NO
10 Correct 2 ms 2648 KB answer = YES
11 Correct 2 ms 2680 KB answer = YES
12 Correct 2 ms 2684 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 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 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2676 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 1 ms 2644 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2676 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2676 KB answer = NO
10 Correct 2 ms 2648 KB answer = YES
11 Correct 2 ms 2680 KB answer = YES
12 Correct 2 ms 2684 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 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 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2676 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 1 ms 2644 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 2680 KB answer = YES
28 Correct 2 ms 2684 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2684 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 1 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 2680 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2676 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2676 KB answer = NO
10 Correct 2 ms 2648 KB answer = YES
11 Correct 2 ms 2680 KB answer = YES
12 Correct 2 ms 2684 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 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 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2676 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 1 ms 2644 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 2680 KB answer = YES
28 Correct 2 ms 2684 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2684 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 1 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES
37 Correct 2 ms 2676 KB answer = YES
38 Correct 2 ms 2676 KB answer = YES
39 Correct 3 ms 2644 KB answer = YES
40 Correct 2 ms 2644 KB answer = YES
41 Correct 2 ms 2680 KB answer = NO
42 Correct 2 ms 2772 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 4 ms 2644 KB answer = YES
45 Correct 2 ms 2684 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 3 ms 2680 KB answer = YES
48 Correct 3 ms 2644 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2676 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2676 KB answer = NO
10 Correct 2 ms 2648 KB answer = YES
11 Correct 2 ms 2680 KB answer = YES
12 Correct 2 ms 2684 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 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 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2676 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 1 ms 2644 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 2680 KB answer = YES
28 Correct 2 ms 2684 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2684 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 1 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES
37 Correct 2 ms 2676 KB answer = YES
38 Correct 2 ms 2676 KB answer = YES
39 Correct 3 ms 2644 KB answer = YES
40 Correct 2 ms 2644 KB answer = YES
41 Correct 2 ms 2680 KB answer = NO
42 Correct 2 ms 2772 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 4 ms 2644 KB answer = YES
45 Correct 2 ms 2684 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 3 ms 2680 KB answer = YES
48 Correct 3 ms 2644 KB answer = YES
49 Correct 10 ms 3456 KB answer = YES
50 Correct 9 ms 3584 KB answer = YES
51 Correct 10 ms 4120 KB answer = YES
52 Correct 7 ms 3456 KB answer = NO
53 Correct 4 ms 2772 KB answer = YES
54 Correct 4 ms 2900 KB answer = YES
55 Correct 6 ms 3028 KB answer = YES
56 Correct 9 ms 3540 KB answer = YES
57 Correct 9 ms 3328 KB answer = YES
58 Correct 12 ms 3404 KB answer = YES
59 Correct 9 ms 3284 KB answer = YES
60 Correct 9 ms 3460 KB answer = YES
61 Correct 5 ms 3028 KB answer = YES
62 Correct 56 ms 9924 KB answer = NO
63 Correct 56 ms 10044 KB answer = YES
64 Correct 53 ms 10112 KB answer = NO
65 Correct 54 ms 10080 KB answer = YES
66 Correct 3 ms 2772 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2676 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2676 KB answer = NO
10 Correct 2 ms 2648 KB answer = YES
11 Correct 2 ms 2680 KB answer = YES
12 Correct 2 ms 2684 KB answer = NO
13 Correct 2 ms 2644 KB answer = YES
14 Correct 2 ms 2644 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 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2676 KB answer = YES
22 Correct 2 ms 2644 KB answer = NO
23 Correct 1 ms 2644 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 2680 KB answer = YES
28 Correct 2 ms 2684 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2684 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 1 ms 2644 KB answer = YES
36 Correct 2 ms 2644 KB answer = YES
37 Correct 2 ms 2676 KB answer = YES
38 Correct 2 ms 2676 KB answer = YES
39 Correct 3 ms 2644 KB answer = YES
40 Correct 2 ms 2644 KB answer = YES
41 Correct 2 ms 2680 KB answer = NO
42 Correct 2 ms 2772 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 4 ms 2644 KB answer = YES
45 Correct 2 ms 2684 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 3 ms 2680 KB answer = YES
48 Correct 3 ms 2644 KB answer = YES
49 Correct 10 ms 3456 KB answer = YES
50 Correct 9 ms 3584 KB answer = YES
51 Correct 10 ms 4120 KB answer = YES
52 Correct 7 ms 3456 KB answer = NO
53 Correct 4 ms 2772 KB answer = YES
54 Correct 4 ms 2900 KB answer = YES
55 Correct 6 ms 3028 KB answer = YES
56 Correct 9 ms 3540 KB answer = YES
57 Correct 9 ms 3328 KB answer = YES
58 Correct 12 ms 3404 KB answer = YES
59 Correct 9 ms 3284 KB answer = YES
60 Correct 9 ms 3460 KB answer = YES
61 Correct 5 ms 3028 KB answer = YES
62 Correct 56 ms 9924 KB answer = NO
63 Correct 56 ms 10044 KB answer = YES
64 Correct 53 ms 10112 KB answer = NO
65 Correct 54 ms 10080 KB answer = YES
66 Correct 3 ms 2772 KB answer = YES
67 Correct 98 ms 20924 KB answer = YES
68 Correct 81 ms 20868 KB answer = YES
69 Correct 79 ms 13728 KB answer = YES
70 Correct 108 ms 18152 KB answer = YES
71 Correct 87 ms 13808 KB answer = YES
72 Correct 114 ms 10556 KB answer = YES
73 Correct 95 ms 9676 KB answer = YES
74 Correct 58 ms 9292 KB answer = YES
75 Correct 25 ms 9736 KB answer = NO
76 Correct 12 ms 3668 KB answer = YES
77 Correct 24 ms 4704 KB answer = YES
78 Correct 42 ms 6148 KB answer = YES
79 Correct 87 ms 9512 KB answer = YES
80 Correct 60 ms 13060 KB answer = YES
81 Correct 56 ms 11200 KB answer = NO
82 Correct 127 ms 13540 KB answer = YES
83 Correct 134 ms 13864 KB answer = YES
84 Correct 136 ms 20900 KB answer = YES
85 Correct 91 ms 20972 KB answer = YES
86 Correct 84 ms 13812 KB answer = YES
87 Correct 64 ms 12252 KB answer = NO
88 Correct 132 ms 11336 KB answer = YES
89 Correct 79 ms 9024 KB answer = YES
90 Correct 85 ms 9032 KB answer = YES
91 Correct 118 ms 9052 KB answer = YES
92 Correct 48 ms 6184 KB answer = YES
93 Correct 64 ms 6080 KB answer = YES
94 Correct 68 ms 20668 KB answer = NO
95 Correct 39 ms 8780 KB answer = NO
96 Correct 194 ms 16352 KB answer = YES
97 Correct 36 ms 20544 KB answer = NO