oj.uz

Submission #1040794

# Submission time Handle Problem Language Result Execution time Memory
1040794 2024-08-01T09:28:12 Z goodspeed0208 Graph (BOI20_graph) C++14
100 / 100
 78 ms 33368 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 = 200005;

/*struct Seg{
	int n;
	vector<int>arr;
	vector<int>tag;
	int clear = 0;
	Seg (int _n) {
		n = _n;
		arr = vector<int>(_n*4, 0);
		tag
	}
	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;
		update()
	}
	void update(int l, int r, int ql, int qr, int a, int c) {
		if (ql <= l && r <= qr) {
			v[i] += 
		}	
	}
	
	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;
	}
};*/

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;
	}
}

bool cmp(pair<int, pii> a, pair<int, pii> b) {
	return (-a.second.second * a.second.first < -b.second.second * b.second.first);
}



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) {
				sort(nums.begin(), nums.end(), cmp);
				/*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();*/
				auto [f, s] = nums[nums.size() / 2].second;
				k = -s * f;
			}
			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:58:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |  auto [f, s] = v[x];
      |       ^
Graph.cpp:59:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |  for (auto [i, c] : G[x]) {
      |            ^
Graph.cpp:71:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |    auto [f2, s2] = v[i];
      |         ^
Graph.cpp: In function 'int main()':
Graph.cpp:135:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |     auto [f, s] = nums[nums.size() / 2].second;
      |          ^
Graph.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |    for (auto [x, vx] : nums) {
      |              ^

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB answer = YES
2 Correct 0 ms 348 KB answer = YES
3 Correct 0 ms 348 KB answer = YES
4 Correct 1 ms 348 KB answer = NO
5 Correct 0 ms 348 KB answer = YES
6 Correct 0 ms 348 KB answer = YES
7 Correct 0 ms 348 KB answer = YES
8 Correct 0 ms 348 KB answer = YES
9 Correct 1 ms 348 KB answer = NO
10 Correct 0 ms 348 KB answer = YES
11 Correct 0 ms 348 KB answer = YES
12 Correct 0 ms 348 KB answer = NO
13 Correct 0 ms 348 KB answer = YES
14 Correct 0 ms 348 KB answer = YES
15 Correct 0 ms 348 KB answer = YES
16 Correct 0 ms 348 KB answer = YES
17 Correct 0 ms 460 KB answer = YES
18 Correct 0 ms 348 KB answer = YES
19 Correct 0 ms 348 KB answer = YES
20 Correct 0 ms 348 KB answer = YES
21 Correct 0 ms 348 KB answer = YES
22 Correct 0 ms 348 KB answer = NO
23 Correct 0 ms 348 KB answer = NO
24 Correct 1 ms 348 KB answer = YES
25 Correct 0 ms 348 KB answer = YES
26 Correct 0 ms 348 KB answer = YES
27 Correct 0 ms 348 KB answer = YES
28 Correct 1 ms 348 KB answer = YES
29 Correct 0 ms 348 KB answer = YES
30 Correct 0 ms 348 KB answer = NO
31 Correct 0 ms 348 KB answer = YES
32 Correct 0 ms 348 KB answer = YES
33 Correct 0 ms 344 KB answer = YES
34 Correct 0 ms 348 KB answer = YES
35 Correct 0 ms 348 KB answer = YES
36 Correct 0 ms 348 KB answer = YES
37 Correct 0 ms 348 KB answer = YES
38 Correct 0 ms 348 KB answer = YES
39 Correct 0 ms 348 KB answer = YES
40 Correct 1 ms 604 KB answer = YES
41 Correct 0 ms 600 KB answer = NO
42 Correct 1 ms 604 KB answer = YES
43 Correct 1 ms 604 KB answer = YES
44 Correct 1 ms 348 KB answer = YES
45 Correct 1 ms 856 KB answer = YES
46 Correct 0 ms 348 KB answer = YES
47 Correct 1 ms 600 KB answer = YES
48 Correct 1 ms 604 KB answer = YES
49 Correct 6 ms 2072 KB answer = YES
50 Correct 6 ms 2392 KB answer = YES
51 Correct 6 ms 2592 KB answer = YES
52 Correct 2 ms 1628 KB answer = NO
53 Correct 1 ms 604 KB answer = YES
54 Correct 1 ms 856 KB answer = YES
55 Correct 3 ms 1308 KB answer = YES
56 Correct 5 ms 1884 KB answer = YES
57 Correct 5 ms 1624 KB answer = YES
58 Correct 4 ms 1744 KB answer = YES
59 Correct 4 ms 1628 KB answer = YES
60 Correct 5 ms 1780 KB answer = YES
61 Correct 2 ms 1172 KB answer = YES
62 Correct 33 ms 12168 KB answer = NO
63 Correct 42 ms 13336 KB answer = YES
64 Correct 31 ms 13224 KB answer = NO
65 Correct 38 ms 13336 KB answer = YES
66 Correct 1 ms 600 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB answer = YES
2 Correct 0 ms 348 KB answer = YES
3 Correct 0 ms 348 KB answer = YES
4 Correct 1 ms 348 KB answer = NO
5 Correct 0 ms 348 KB answer = YES
6 Correct 0 ms 348 KB answer = YES
7 Correct 0 ms 348 KB answer = YES
8 Correct 0 ms 348 KB answer = YES
9 Correct 1 ms 348 KB answer = NO
10 Correct 0 ms 348 KB answer = YES
11 Correct 0 ms 348 KB answer = YES
12 Correct 0 ms 348 KB answer = NO
13 Correct 0 ms 348 KB answer = YES
14 Correct 0 ms 348 KB answer = YES
15 Correct 0 ms 348 KB answer = YES
16 Correct 0 ms 348 KB answer = YES
17 Correct 0 ms 460 KB answer = YES
18 Correct 0 ms 348 KB answer = YES
19 Correct 0 ms 348 KB answer = YES
20 Correct 0 ms 348 KB answer = YES
21 Correct 0 ms 348 KB answer = YES
22 Correct 0 ms 348 KB answer = NO
23 Correct 0 ms 348 KB answer = NO
24 Correct 1 ms 348 KB answer = YES
25 Correct 0 ms 348 KB answer = YES
26 Correct 0 ms 348 KB answer = YES
27 Correct 0 ms 348 KB answer = YES
28 Correct 1 ms 348 KB answer = YES
29 Correct 0 ms 348 KB answer = YES
30 Correct 0 ms 348 KB answer = NO
31 Correct 0 ms 348 KB answer = YES
32 Correct 0 ms 348 KB answer = YES
33 Correct 0 ms 344 KB answer = YES
34 Correct 0 ms 348 KB answer = YES
35 Correct 0 ms 348 KB answer = YES
36 Correct 0 ms 348 KB answer = YES
37 Correct 0 ms 348 KB answer = YES
38 Correct 0 ms 348 KB answer = YES
39 Correct 0 ms 348 KB answer = YES
40 Correct 1 ms 604 KB answer = YES
41 Correct 0 ms 600 KB answer = NO
42 Correct 1 ms 604 KB answer = YES
43 Correct 1 ms 604 KB answer = YES
44 Correct 1 ms 348 KB answer = YES
45 Correct 1 ms 856 KB answer = YES
46 Correct 0 ms 348 KB answer = YES
47 Correct 1 ms 600 KB answer = YES
48 Correct 1 ms 604 KB answer = YES
49 Correct 6 ms 2072 KB answer = YES
50 Correct 6 ms 2392 KB answer = YES
51 Correct 6 ms 2592 KB answer = YES
52 Correct 2 ms 1628 KB answer = NO
53 Correct 1 ms 604 KB answer = YES
54 Correct 1 ms 856 KB answer = YES
55 Correct 3 ms 1308 KB answer = YES
56 Correct 5 ms 1884 KB answer = YES
57 Correct 5 ms 1624 KB answer = YES
58 Correct 4 ms 1744 KB answer = YES
59 Correct 4 ms 1628 KB answer = YES
60 Correct 5 ms 1780 KB answer = YES
61 Correct 2 ms 1172 KB answer = YES
62 Correct 33 ms 12168 KB answer = NO
63 Correct 42 ms 13336 KB answer = YES
64 Correct 31 ms 13224 KB answer = NO
65 Correct 38 ms 13336 KB answer = YES
66 Correct 1 ms 600 KB answer = YES
67 Correct 57 ms 25536 KB answer = YES
68 Correct 55 ms 25532 KB answer = YES
69 Correct 43 ms 25284 KB answer = YES
70 Correct 60 ms 33368 KB answer = YES
71 Correct 48 ms 25792 KB answer = YES
72 Correct 51 ms 15304 KB answer = YES
73 Correct 48 ms 15568 KB answer = YES
74 Correct 34 ms 15420 KB answer = YES
75 Correct 16 ms 10960 KB answer = NO
76 Correct 7 ms 2140 KB answer = YES
77 Correct 12 ms 4052 KB answer = YES
78 Correct 23 ms 6864 KB answer = YES
79 Correct 52 ms 13000 KB answer = YES
80 Correct 39 ms 15300 KB answer = YES
81 Correct 31 ms 20164 KB answer = NO
82 Correct 55 ms 24516 KB answer = YES
83 Correct 65 ms 26056 KB answer = YES
84 Correct 65 ms 26308 KB answer = YES
85 Correct 60 ms 25660 KB answer = YES
86 Correct 49 ms 25536 KB answer = YES
87 Correct 30 ms 15564 KB answer = NO
88 Correct 60 ms 18376 KB answer = YES
89 Correct 45 ms 11860 KB answer = YES
90 Correct 48 ms 11860 KB answer = YES
91 Correct 48 ms 12628 KB answer = YES
92 Correct 24 ms 7632 KB answer = YES
93 Correct 23 ms 7640 KB answer = YES
94 Correct 37 ms 25040 KB answer = NO
95 Correct 22 ms 11608 KB answer = NO
96 Correct 78 ms 28868 KB answer = YES
97 Correct 24 ms 24772 KB answer = NO