oj.uz

Submission #1040028

# Submission time Handle Problem Language Result Execution time Memory
1040028 2024-07-31T14:14:38 Z goodspeed0208 Graph (BOI20_graph) C++14
58 / 100
 700 ms 25800 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<long long, long long>
#define INF 1000000000000000000
using namespace std;

int n, m;
vector<vector<pii> >G;
vector<pii>v;
double k = 0;
int can = -1; // -1 unknown 0 wrong 1 can
int N = 20005;

struct Seg{
	int n;
	vector<int>arr;
	Seg (int _n) {
		n = _n;
		arr = vector<int>(_n*4, 0);
	}
	void clear() {
		for (int i = 0 ; i < n*4 ; i++) {
			arr[i] = 0;
		}
	}
	void add(int l, int r, int a, int c) { //c == 0 left c == 1 right
		l += N, r += N;
		if (c == 0) {
			for (int i = r ; i >= l ; i--) {
				arr[i] += a;
				a++;
			}
		} else {
			for (int i = l ; i <= r ; i++) {
				arr[i] += a;
				a++;
			}
		}
			
	}
	int query(int l, int r) {
		l += N, r += N;
		int ans = INF, pos;
		for (int i = l ; i <= r ; i++) {
			if (arr[i] < ans){
				ans = arr[i];
				pos = i;
			} 
		}
		return pos;
	}
	/*void add(int l, int r, int ql, int qr, int a, int i) {
		if (ql <= l && r <= qr) {
			arr[i] += 
		}
	}*/
};

vector<pair<int, pii> >nums;
vector<double>ans;

void dfs(int x, int p) {
	nums.push_back({x, v[x]});
	if (can == 0) return;
	auto [f, s] = v[x];
	for (auto [i, c] : G[x]) {
		//if (i == p && kind == c) continue;
		/*if (i == x) {
			double newk = (double)(c - s) / f;
			if (can == 1) {
				if (k != newk) can = 0;
			} else {
				k = newk; can = 1;
			}
			continue;
		}*/
		if (v[i].first != 0) {
			auto [f2, s2] = v[i];
			if (f == -f2) {
				if (s + s2 != c) can = 0;
			} else {
				double newk = (double)(c - s - s2) / (f + f2);
				if (can == 1) {
					if (k != newk) can = 0;
				} else {
					k = newk; can = 1;
				}
			}
			continue;
		}
		if (c == 1) v[i] = {-f, 1-s};
		else v[i] = {-f, 2-s};
		dfs(i, x);
		if (can == 0) return;
	}
}



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	G.resize(n);
	v = vector<pii>(n, {0ll, 0ll});
	ans.resize(n);
	for (int i = 0 ; i < m ; i++) {
		int a, b, c;
		cin >> a >> b >> c; a--, b--;
		G[a].push_back({b, c});
		G[b].push_back({a, c});
	}
	Seg seg(N*2);
	for (int i = 0 ; i < n ; i++) {
		if (v[i].first == 0) {
			v[i] = {1, 0};
			can = -1;
			dfs(i, -1);
			if (can == 0) {
				cout << "NO\n";
				return 0;
			}
			if (can == -1) {
				for (auto [x, vx] : nums) {
					auto [f, s] = vx;
					//cout << f << " " << s <<"\n";
					if (f == 1) {
						seg.add(-N, -s, 0, 0);
						seg.add(-s, N, 0, 1);
					} else {
						seg.add(s, N, 0, 1);
						seg.add(-N, s, 0, 0);
					}
				}
				k = seg.query(-N, N) - N;
				seg.clear();
			}
			for (auto [x, vx] : nums) {
				ans[x] = k * vx.first + vx.second;
			}
			nums.clear();
			//cout << i << " " << can << " " << k << "\n";
		}
	}
	cout << "YES\n";
	for (int i = 0 ; i < n ; i++) {
		cout << fixed << setprecision(6) << ans[i] << " ";
	}
	cout << "\n";
}

Compilation message

Graph.cpp: In function 'void dfs(long long int, long long int)':
Graph.cpp:65:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  auto [f, s] = v[x];
      |       ^
Graph.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |  for (auto [i, c] : G[x]) {
      |            ^
Graph.cpp:78:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |    auto [f2, s2] = v[i];
      |         ^
Graph.cpp: In function 'int main()':
Graph.cpp:124:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     for (auto [x, vx] : nums) {
      |               ^
Graph.cpp:125:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |      auto [f, s] = vx;
      |           ^
Graph.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |    for (auto [x, vx] : nums) {
      |              ^
Graph.cpp:135:26: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |     k = seg.query(-N, N) - N;
      |         ~~~~~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB answer = YES
2 Correct 1 ms 1628 KB answer = YES
3 Correct 1 ms 1476 KB answer = YES
4 Correct 1 ms 1628 KB answer = NO
5 Correct 1 ms 1628 KB answer = YES
6 Correct 1 ms 1628 KB answer = YES
7 Correct 1 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 0 ms 1628 KB answer = NO
10 Correct 0 ms 1628 KB answer = YES
11 Correct 1 ms 1628 KB answer = YES
12 Correct 1 ms 1628 KB answer = NO
13 Correct 1 ms 1628 KB answer = YES
14 Correct 1 ms 1476 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1540 KB answer = YES
18 Correct 1 ms 1628 KB answer = YES
19 Correct 1 ms 1628 KB answer = YES
20 Correct 0 ms 1628 KB answer = YES
21 Correct 1 ms 1628 KB answer = YES
22 Correct 1 ms 1628 KB answer = NO
23 Correct 1 ms 1628 KB answer = NO
24 Correct 3 ms 1624 KB answer = YES
25 Correct 2 ms 1628 KB answer = YES
26 Correct 3 ms 1628 KB answer = YES
27 Correct 1 ms 1628 KB answer = YES
28 Correct 1 ms 1628 KB answer = YES
29 Correct 2 ms 1628 KB answer = YES
30 Correct 1 ms 1480 KB answer = NO
31 Correct 1 ms 1628 KB answer = YES
32 Correct 1 ms 1628 KB answer = YES
33 Correct 6 ms 1628 KB answer = YES
34 Correct 2 ms 1628 KB answer = YES
35 Correct 1 ms 1628 KB answer = YES
36 Correct 1 ms 1624 KB answer = YES
37 Correct 4 ms 1628 KB answer = YES
38 Correct 1 ms 1628 KB answer = YES
39 Correct 8 ms 1832 KB answer = YES
40 Correct 1 ms 1884 KB answer = YES
41 Correct 1 ms 1884 KB answer = NO
42 Correct 12 ms 1900 KB answer = YES
43 Correct 13 ms 1628 KB answer = YES
44 Correct 14 ms 1628 KB answer = YES
45 Correct 1 ms 1628 KB answer = YES
46 Correct 8 ms 1808 KB answer = YES
47 Correct 1 ms 1880 KB answer = YES
48 Correct 1 ms 1884 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB answer = YES
2 Correct 1 ms 1628 KB answer = YES
3 Correct 1 ms 1476 KB answer = YES
4 Correct 1 ms 1628 KB answer = NO
5 Correct 1 ms 1628 KB answer = YES
6 Correct 1 ms 1628 KB answer = YES
7 Correct 1 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 0 ms 1628 KB answer = NO
10 Correct 0 ms 1628 KB answer = YES
11 Correct 1 ms 1628 KB answer = YES
12 Correct 1 ms 1628 KB answer = NO
13 Correct 1 ms 1628 KB answer = YES
14 Correct 1 ms 1476 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1540 KB answer = YES
18 Correct 1 ms 1628 KB answer = YES
19 Correct 1 ms 1628 KB answer = YES
20 Correct 0 ms 1628 KB answer = YES
21 Correct 1 ms 1628 KB answer = YES
22 Correct 1 ms 1628 KB answer = NO
23 Correct 1 ms 1628 KB answer = NO
24 Correct 3 ms 1624 KB answer = YES
25 Correct 2 ms 1628 KB answer = YES
26 Correct 3 ms 1628 KB answer = YES
27 Correct 1 ms 1628 KB answer = YES
28 Correct 1 ms 1628 KB answer = YES
29 Correct 2 ms 1628 KB answer = YES
30 Correct 1 ms 1480 KB answer = NO
31 Correct 1 ms 1628 KB answer = YES
32 Correct 1 ms 1628 KB answer = YES
33 Correct 6 ms 1628 KB answer = YES
34 Correct 2 ms 1628 KB answer = YES
35 Correct 1 ms 1628 KB answer = YES
36 Correct 1 ms 1624 KB answer = YES
37 Correct 4 ms 1628 KB answer = YES
38 Correct 1 ms 1628 KB answer = YES
39 Correct 8 ms 1832 KB answer = YES
40 Correct 1 ms 1884 KB answer = YES
41 Correct 1 ms 1884 KB answer = NO
42 Correct 12 ms 1900 KB answer = YES
43 Correct 13 ms 1628 KB answer = YES
44 Correct 14 ms 1628 KB answer = YES
45 Correct 1 ms 1628 KB answer = YES
46 Correct 8 ms 1808 KB answer = YES
47 Correct 1 ms 1880 KB answer = YES
48 Correct 1 ms 1884 KB answer = YES
49 Correct 129 ms 3160 KB answer = YES
50 Correct 6 ms 3672 KB answer = YES
51 Correct 127 ms 3868 KB answer = YES
52 Correct 3 ms 2908 KB answer = NO
53 Correct 13 ms 1884 KB answer = YES
54 Correct 30 ms 2116 KB answer = YES
55 Correct 65 ms 2392 KB answer = YES
56 Correct 123 ms 3160 KB answer = YES
57 Correct 213 ms 2868 KB answer = YES
58 Correct 112 ms 2900 KB answer = YES
59 Correct 5 ms 3032 KB answer = YES
60 Correct 126 ms 3096 KB answer = YES
61 Correct 3 ms 2648 KB answer = YES
62 Correct 33 ms 13404 KB answer = NO
63 Correct 36 ms 14612 KB answer = YES
64 Correct 34 ms 14572 KB answer = NO
65 Correct 38 ms 14616 KB answer = YES
66 Correct 25 ms 1880 KB answer = YES

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB answer = YES
2 Correct 1 ms 1628 KB answer = YES
3 Correct 1 ms 1476 KB answer = YES
4 Correct 1 ms 1628 KB answer = NO
5 Correct 1 ms 1628 KB answer = YES
6 Correct 1 ms 1628 KB answer = YES
7 Correct 1 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 0 ms 1628 KB answer = NO
10 Correct 0 ms 1628 KB answer = YES
11 Correct 1 ms 1628 KB answer = YES
12 Correct 1 ms 1628 KB answer = NO
13 Correct 1 ms 1628 KB answer = YES
14 Correct 1 ms 1476 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1540 KB answer = YES
18 Correct 1 ms 1628 KB answer = YES
19 Correct 1 ms 1628 KB answer = YES
20 Correct 0 ms 1628 KB answer = YES
21 Correct 1 ms 1628 KB answer = YES
22 Correct 1 ms 1628 KB answer = NO
23 Correct 1 ms 1628 KB answer = NO
24 Correct 3 ms 1624 KB answer = YES
25 Correct 2 ms 1628 KB answer = YES
26 Correct 3 ms 1628 KB answer = YES
27 Correct 1 ms 1628 KB answer = YES
28 Correct 1 ms 1628 KB answer = YES
29 Correct 2 ms 1628 KB answer = YES
30 Correct 1 ms 1480 KB answer = NO
31 Correct 1 ms 1628 KB answer = YES
32 Correct 1 ms 1628 KB answer = YES
33 Correct 6 ms 1628 KB answer = YES
34 Correct 2 ms 1628 KB answer = YES
35 Correct 1 ms 1628 KB answer = YES
36 Correct 1 ms 1624 KB answer = YES
37 Correct 4 ms 1628 KB answer = YES
38 Correct 1 ms 1628 KB answer = YES
39 Correct 8 ms 1832 KB answer = YES
40 Correct 1 ms 1884 KB answer = YES
41 Correct 1 ms 1884 KB answer = NO
42 Correct 12 ms 1900 KB answer = YES
43 Correct 13 ms 1628 KB answer = YES
44 Correct 14 ms 1628 KB answer = YES
45 Correct 1 ms 1628 KB answer = YES
46 Correct 8 ms 1808 KB answer = YES
47 Correct 1 ms 1880 KB answer = YES
48 Correct 1 ms 1884 KB answer = YES
49 Correct 129 ms 3160 KB answer = YES
50 Correct 6 ms 3672 KB answer = YES
51 Correct 127 ms 3868 KB answer = YES
52 Correct 3 ms 2908 KB answer = NO
53 Correct 13 ms 1884 KB answer = YES
54 Correct 30 ms 2116 KB answer = YES
55 Correct 65 ms 2392 KB answer = YES
56 Correct 123 ms 3160 KB answer = YES
57 Correct 213 ms 2868 KB answer = YES
58 Correct 112 ms 2900 KB answer = YES
59 Correct 5 ms 3032 KB answer = YES
60 Correct 126 ms 3096 KB answer = YES
61 Correct 3 ms 2648 KB answer = YES
62 Correct 33 ms 13404 KB answer = NO
63 Correct 36 ms 14612 KB answer = YES
64 Correct 34 ms 14572 KB answer = NO
65 Correct 38 ms 14616 KB answer = YES
66 Correct 25 ms 1880 KB answer = YES
67 Execution timed out 1022 ms 25800 KB Time limit exceeded
68 Halted 0 ms 0 KB -