oj.uz

Submission #536336

# Submission time Handle Problem Language Result Execution time Memory
536336 2022-03-13T01:39:13 Z skittles1412 Graph (BOI20_graph) C++17
100 / 100
 190 ms 30612 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

using ld = long double;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 1e5;
const ld UNKNOWN = 1e9, EPS = 1e-6;

vector<int> vals;
vector<pair<int, int>> graph[maxn];
bool found, vis[maxn];
int depth[maxn];
ld ans[maxn];

void dfs2(int u) {
	for (auto& [v, e] : graph[u]) {
		if (ans[v] == UNKNOWN) {
			ans[v] = e - ans[u];
			dfs2(v);
		} else if (abs(e - ans[u] - ans[v]) > EPS) {
			dbg(u, v, ans[u], ans[v]);
			cout << "NO" << endl;
			exit(0);
		}
	}
}

void dfs1(int u, int d) {
	static vector<pair<int, int>> st;
	if (found) {
		return;
	}
	if (vis[u]) {
		if ((d - depth[u]) % 2 == 0) {
			return;
		}
		found = true;
		ld sum = 0;
		vector<pair<int, int>> cur;
		for (int i = sz(st) - 1; i >= 0; i--) {
			if (i < sz(st) - 1 && st[i].first == u) {
				break;
			}
			cur.push_back(st[i]);
		}
		for (auto& [_, x] : cur) {
			sum += x;
		}
		sum /= 2;
		for (int i = 1; i < sz(cur); i += 2) {
			sum -= cur[i].second;
		}
		dbg(cur[0].first, sum);
		ans[cur[0].first] = sum;
		dfs2(cur[0].first);
		return;
	}
	vis[u] = true;
	depth[u] = d;
	for (auto& [v, e] : graph[u]) {
		st.emplace_back(v, e);
		dfs1(v, d + 1);
		st.pop_back();
	}
}

void dfs3(int u, int s, bool neg) {
	if (vis[u]) {
		return;
	}
	dbg(s);
	if (neg) {
		vals.push_back(-s);
	} else {
		vals.push_back(s);
	}
	vis[u] = true;
	for (auto& [v, e] : graph[u]) {
		dfs3(v, e - s, !neg);
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	int edges[m][3];
	for (auto& [u, v, w] : edges) {
		cin >> u >> v >> w;
		u--;
		v--;
		graph[u].emplace_back(v, w);
		graph[v].emplace_back(u, w);
	}
	fill(begin(ans), end(ans), UNKNOWN);
	for (int i = 0; i < n; i++) {
		if (!vis[i] && ans[i] == UNKNOWN) {
			found = false;
			dbg(i);
			dfs1(i, 0);
		}
	}
	memset(vis, 0, sizeof(vis));
	dbg("A");
	for (int i = 0; i < n; i++) {
		if (ans[i] == UNKNOWN) {
			vals.clear();
			dfs3(i, 0, true);
			sort(begin(vals), end(vals));
			ans[i] = vals[sz(vals) / 2];
			dfs2(i);
		}
	}
	for (auto& [u, v, w] : edges) {
		assert(abs(w - ans[u] - ans[v]) <= EPS);
	}
	cout << "YES" << endl;
	for (int i = 0; i < n; i++) {
		cout << ans[i] << " \n"[i == n - 1];
	}
}

int main() {
	cout << fixed << setprecision(9);
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB answer = YES
2 Correct 3 ms 4220 KB answer = YES
3 Correct 2 ms 4344 KB answer = YES
4 Correct 2 ms 4216 KB answer = NO
5 Correct 2 ms 4308 KB answer = YES
6 Correct 3 ms 4308 KB answer = YES
7 Correct 2 ms 4308 KB answer = YES
8 Correct 2 ms 4308 KB answer = YES
9 Correct 2 ms 4308 KB answer = NO
10 Correct 2 ms 4308 KB answer = YES
11 Correct 2 ms 4308 KB answer = YES
12 Correct 2 ms 4308 KB answer = NO
13 Correct 2 ms 4308 KB answer = YES
14 Correct 3 ms 4220 KB answer = YES
15 Correct 2 ms 4256 KB answer = YES
16 Correct 3 ms 4308 KB answer = YES
17 Correct 3 ms 4308 KB answer = YES
18 Correct 2 ms 4308 KB answer = YES
19 Correct 2 ms 4224 KB answer = YES
20 Correct 3 ms 4308 KB answer = YES
21 Correct 2 ms 4308 KB answer = YES
22 Correct 3 ms 4308 KB answer = NO
23 Correct 3 ms 4180 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB answer = YES
2 Correct 3 ms 4220 KB answer = YES
3 Correct 2 ms 4344 KB answer = YES
4 Correct 2 ms 4216 KB answer = NO
5 Correct 2 ms 4308 KB answer = YES
6 Correct 3 ms 4308 KB answer = YES
7 Correct 2 ms 4308 KB answer = YES
8 Correct 2 ms 4308 KB answer = YES
9 Correct 2 ms 4308 KB answer = NO
10 Correct 2 ms 4308 KB answer = YES
11 Correct 2 ms 4308 KB answer = YES
12 Correct 2 ms 4308 KB answer = NO
13 Correct 2 ms 4308 KB answer = YES
14 Correct 3 ms 4220 KB answer = YES
15 Correct 2 ms 4256 KB answer = YES
16 Correct 3 ms 4308 KB answer = YES
17 Correct 3 ms 4308 KB answer = YES
18 Correct 2 ms 4308 KB answer = YES
19 Correct 2 ms 4224 KB answer = YES
20 Correct 3 ms 4308 KB answer = YES
21 Correct 2 ms 4308 KB answer = YES
22 Correct 3 ms 4308 KB answer = NO
23 Correct 3 ms 4180 KB answer = NO
24 Correct 2 ms 4308 KB answer = YES
25 Correct 3 ms 4280 KB answer = YES
26 Correct 4 ms 4308 KB answer = YES
27 Correct 3 ms 4352 KB answer = YES
28 Correct 3 ms 4308 KB answer = YES
29 Correct 3 ms 4308 KB answer = YES
30 Correct 3 ms 4436 KB answer = NO
31 Correct 3 ms 4308 KB answer = YES
32 Correct 3 ms 4308 KB answer = YES
33 Correct 3 ms 4308 KB answer = YES
34 Correct 3 ms 4308 KB answer = YES
35 Correct 3 ms 4308 KB answer = YES
36 Correct 2 ms 4348 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB answer = YES
2 Correct 3 ms 4220 KB answer = YES
3 Correct 2 ms 4344 KB answer = YES
4 Correct 2 ms 4216 KB answer = NO
5 Correct 2 ms 4308 KB answer = YES
6 Correct 3 ms 4308 KB answer = YES
7 Correct 2 ms 4308 KB answer = YES
8 Correct 2 ms 4308 KB answer = YES
9 Correct 2 ms 4308 KB answer = NO
10 Correct 2 ms 4308 KB answer = YES
11 Correct 2 ms 4308 KB answer = YES
12 Correct 2 ms 4308 KB answer = NO
13 Correct 2 ms 4308 KB answer = YES
14 Correct 3 ms 4220 KB answer = YES
15 Correct 2 ms 4256 KB answer = YES
16 Correct 3 ms 4308 KB answer = YES
17 Correct 3 ms 4308 KB answer = YES
18 Correct 2 ms 4308 KB answer = YES
19 Correct 2 ms 4224 KB answer = YES
20 Correct 3 ms 4308 KB answer = YES
21 Correct 2 ms 4308 KB answer = YES
22 Correct 3 ms 4308 KB answer = NO
23 Correct 3 ms 4180 KB answer = NO
24 Correct 2 ms 4308 KB answer = YES
25 Correct 3 ms 4280 KB answer = YES
26 Correct 4 ms 4308 KB answer = YES
27 Correct 3 ms 4352 KB answer = YES
28 Correct 3 ms 4308 KB answer = YES
29 Correct 3 ms 4308 KB answer = YES
30 Correct 3 ms 4436 KB answer = NO
31 Correct 3 ms 4308 KB answer = YES
32 Correct 3 ms 4308 KB answer = YES
33 Correct 3 ms 4308 KB answer = YES
34 Correct 3 ms 4308 KB answer = YES
35 Correct 3 ms 4308 KB answer = YES
36 Correct 2 ms 4348 KB answer = YES
37 Correct 3 ms 4344 KB answer = YES
38 Correct 2 ms 4308 KB answer = YES
39 Correct 4 ms 4308 KB answer = YES
40 Correct 3 ms 4436 KB answer = YES
41 Correct 3 ms 4308 KB answer = NO
42 Correct 3 ms 4436 KB answer = YES
43 Correct 3 ms 4308 KB answer = YES
44 Correct 3 ms 4360 KB answer = YES
45 Correct 3 ms 4436 KB answer = YES
46 Correct 3 ms 4348 KB answer = YES
47 Correct 3 ms 4308 KB answer = YES
48 Correct 3 ms 4356 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB answer = YES
2 Correct 3 ms 4220 KB answer = YES
3 Correct 2 ms 4344 KB answer = YES
4 Correct 2 ms 4216 KB answer = NO
5 Correct 2 ms 4308 KB answer = YES
6 Correct 3 ms 4308 KB answer = YES
7 Correct 2 ms 4308 KB answer = YES
8 Correct 2 ms 4308 KB answer = YES
9 Correct 2 ms 4308 KB answer = NO
10 Correct 2 ms 4308 KB answer = YES
11 Correct 2 ms 4308 KB answer = YES
12 Correct 2 ms 4308 KB answer = NO
13 Correct 2 ms 4308 KB answer = YES
14 Correct 3 ms 4220 KB answer = YES
15 Correct 2 ms 4256 KB answer = YES
16 Correct 3 ms 4308 KB answer = YES
17 Correct 3 ms 4308 KB answer = YES
18 Correct 2 ms 4308 KB answer = YES
19 Correct 2 ms 4224 KB answer = YES
20 Correct 3 ms 4308 KB answer = YES
21 Correct 2 ms 4308 KB answer = YES
22 Correct 3 ms 4308 KB answer = NO
23 Correct 3 ms 4180 KB answer = NO
24 Correct 2 ms 4308 KB answer = YES
25 Correct 3 ms 4280 KB answer = YES
26 Correct 4 ms 4308 KB answer = YES
27 Correct 3 ms 4352 KB answer = YES
28 Correct 3 ms 4308 KB answer = YES
29 Correct 3 ms 4308 KB answer = YES
30 Correct 3 ms 4436 KB answer = NO
31 Correct 3 ms 4308 KB answer = YES
32 Correct 3 ms 4308 KB answer = YES
33 Correct 3 ms 4308 KB answer = YES
34 Correct 3 ms 4308 KB answer = YES
35 Correct 3 ms 4308 KB answer = YES
36 Correct 2 ms 4348 KB answer = YES
37 Correct 3 ms 4344 KB answer = YES
38 Correct 2 ms 4308 KB answer = YES
39 Correct 4 ms 4308 KB answer = YES
40 Correct 3 ms 4436 KB answer = YES
41 Correct 3 ms 4308 KB answer = NO
42 Correct 3 ms 4436 KB answer = YES
43 Correct 3 ms 4308 KB answer = YES
44 Correct 3 ms 4360 KB answer = YES
45 Correct 3 ms 4436 KB answer = YES
46 Correct 3 ms 4348 KB answer = YES
47 Correct 3 ms 4308 KB answer = YES
48 Correct 3 ms 4356 KB answer = YES
49 Correct 11 ms 5124 KB answer = YES
50 Correct 11 ms 5616 KB answer = YES
51 Correct 12 ms 5588 KB answer = YES
52 Correct 6 ms 5512 KB answer = NO
53 Correct 3 ms 4436 KB answer = YES
54 Correct 4 ms 4436 KB answer = YES
55 Correct 8 ms 4884 KB answer = YES
56 Correct 11 ms 5140 KB answer = YES
57 Correct 11 ms 5076 KB answer = YES
58 Correct 10 ms 5076 KB answer = YES
59 Correct 10 ms 4956 KB answer = YES
60 Correct 11 ms 5056 KB answer = YES
61 Correct 6 ms 4612 KB answer = YES
62 Correct 54 ms 13616 KB answer = NO
63 Correct 60 ms 14032 KB answer = YES
64 Correct 54 ms 13888 KB answer = NO
65 Correct 59 ms 14076 KB answer = YES
66 Correct 4 ms 4436 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB answer = YES
2 Correct 3 ms 4220 KB answer = YES
3 Correct 2 ms 4344 KB answer = YES
4 Correct 2 ms 4216 KB answer = NO
5 Correct 2 ms 4308 KB answer = YES
6 Correct 3 ms 4308 KB answer = YES
7 Correct 2 ms 4308 KB answer = YES
8 Correct 2 ms 4308 KB answer = YES
9 Correct 2 ms 4308 KB answer = NO
10 Correct 2 ms 4308 KB answer = YES
11 Correct 2 ms 4308 KB answer = YES
12 Correct 2 ms 4308 KB answer = NO
13 Correct 2 ms 4308 KB answer = YES
14 Correct 3 ms 4220 KB answer = YES
15 Correct 2 ms 4256 KB answer = YES
16 Correct 3 ms 4308 KB answer = YES
17 Correct 3 ms 4308 KB answer = YES
18 Correct 2 ms 4308 KB answer = YES
19 Correct 2 ms 4224 KB answer = YES
20 Correct 3 ms 4308 KB answer = YES
21 Correct 2 ms 4308 KB answer = YES
22 Correct 3 ms 4308 KB answer = NO
23 Correct 3 ms 4180 KB answer = NO
24 Correct 2 ms 4308 KB answer = YES
25 Correct 3 ms 4280 KB answer = YES
26 Correct 4 ms 4308 KB answer = YES
27 Correct 3 ms 4352 KB answer = YES
28 Correct 3 ms 4308 KB answer = YES
29 Correct 3 ms 4308 KB answer = YES
30 Correct 3 ms 4436 KB answer = NO
31 Correct 3 ms 4308 KB answer = YES
32 Correct 3 ms 4308 KB answer = YES
33 Correct 3 ms 4308 KB answer = YES
34 Correct 3 ms 4308 KB answer = YES
35 Correct 3 ms 4308 KB answer = YES
36 Correct 2 ms 4348 KB answer = YES
37 Correct 3 ms 4344 KB answer = YES
38 Correct 2 ms 4308 KB answer = YES
39 Correct 4 ms 4308 KB answer = YES
40 Correct 3 ms 4436 KB answer = YES
41 Correct 3 ms 4308 KB answer = NO
42 Correct 3 ms 4436 KB answer = YES
43 Correct 3 ms 4308 KB answer = YES
44 Correct 3 ms 4360 KB answer = YES
45 Correct 3 ms 4436 KB answer = YES
46 Correct 3 ms 4348 KB answer = YES
47 Correct 3 ms 4308 KB answer = YES
48 Correct 3 ms 4356 KB answer = YES
49 Correct 11 ms 5124 KB answer = YES
50 Correct 11 ms 5616 KB answer = YES
51 Correct 12 ms 5588 KB answer = YES
52 Correct 6 ms 5512 KB answer = NO
53 Correct 3 ms 4436 KB answer = YES
54 Correct 4 ms 4436 KB answer = YES
55 Correct 8 ms 4884 KB answer = YES
56 Correct 11 ms 5140 KB answer = YES
57 Correct 11 ms 5076 KB answer = YES
58 Correct 10 ms 5076 KB answer = YES
59 Correct 10 ms 4956 KB answer = YES
60 Correct 11 ms 5056 KB answer = YES
61 Correct 6 ms 4612 KB answer = YES
62 Correct 54 ms 13616 KB answer = NO
63 Correct 60 ms 14032 KB answer = YES
64 Correct 54 ms 13888 KB answer = NO
65 Correct 59 ms 14076 KB answer = YES
66 Correct 4 ms 4436 KB answer = YES
67 Correct 96 ms 21184 KB answer = YES
68 Correct 84 ms 21024 KB answer = YES
69 Correct 83 ms 24908 KB answer = YES
70 Correct 113 ms 30612 KB answer = YES
71 Correct 89 ms 24984 KB answer = YES
72 Correct 107 ms 12684 KB answer = YES
73 Correct 99 ms 12184 KB answer = YES
74 Correct 64 ms 13188 KB answer = YES
75 Correct 33 ms 13124 KB answer = NO
76 Correct 14 ms 5264 KB answer = YES
77 Correct 25 ms 6400 KB answer = YES
78 Correct 46 ms 7916 KB answer = YES
79 Correct 99 ms 11592 KB answer = YES
80 Correct 70 ms 14068 KB answer = YES
81 Correct 42 ms 16748 KB answer = NO
82 Correct 102 ms 20576 KB answer = YES
83 Correct 136 ms 25148 KB answer = YES
84 Correct 141 ms 21132 KB answer = YES
85 Correct 97 ms 21204 KB answer = YES
86 Correct 95 ms 25064 KB answer = YES
87 Correct 74 ms 15148 KB answer = NO
88 Correct 131 ms 17300 KB answer = YES
89 Correct 102 ms 11524 KB answer = YES
90 Correct 118 ms 11528 KB answer = YES
91 Correct 131 ms 11636 KB answer = YES
92 Correct 49 ms 8184 KB answer = YES
93 Correct 64 ms 8144 KB answer = YES
94 Correct 103 ms 19768 KB answer = NO
95 Correct 50 ms 10316 KB answer = NO
96 Correct 190 ms 19980 KB answer = YES
97 Correct 45 ms 19776 KB answer = NO