oj.uz

Submission #1040007

# Submission time Handle Problem Language Result Execution time Memory
1040007 2024-07-31T13:57:09 Z goodspeed0208 Graph (BOI20_graph) C++14
0 / 100
 1 ms 1628 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) 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;
			}
			//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:69:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |    auto [f2, s2] = v[i];
      |         ^
Graph.cpp: In function 'int main()':
Graph.cpp:115:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |     for (auto [x, vx] : nums) {
      |               ^
Graph.cpp:116:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |      auto [f, s] = vx;
      |           ^
Graph.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |    for (auto [x, vx] : nums) {
      |              ^
Graph.cpp:126:26: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |     k = seg.query(-N, N) - N;
      |         ~~~~~~~~~~~~~~~~~^~~

Subtask #1
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 1628 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 0 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 1 ms 1628 KB answer = NO
10 Correct 1 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 1628 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1628 KB answer = YES
18 Correct 0 ms 1520 KB answer = YES
19 Incorrect 1 ms 1628 KB Sum of endpoints for edge (1; 1) differs from the expected value 2.
20 Halted 0 ms 0 KB -

Subtask #2
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 1628 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 0 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 1 ms 1628 KB answer = NO
10 Correct 1 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 1628 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1628 KB answer = YES
18 Correct 0 ms 1520 KB answer = YES
19 Incorrect 1 ms 1628 KB Sum of endpoints for edge (1; 1) differs from the expected value 2.
20 Halted 0 ms 0 KB -

Subtask #3
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 1628 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 0 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 1 ms 1628 KB answer = NO
10 Correct 1 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 1628 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1628 KB answer = YES
18 Correct 0 ms 1520 KB answer = YES
19 Incorrect 1 ms 1628 KB Sum of endpoints for edge (1; 1) differs from the expected value 2.
20 Halted 0 ms 0 KB -

Subtask #4
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 1628 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 0 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 1 ms 1628 KB answer = NO
10 Correct 1 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 1628 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1628 KB answer = YES
18 Correct 0 ms 1520 KB answer = YES
19 Incorrect 1 ms 1628 KB Sum of endpoints for edge (1; 1) differs from the expected value 2.
20 Halted 0 ms 0 KB -

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 1628 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 0 ms 1628 KB answer = YES
8 Correct 1 ms 1628 KB answer = YES
9 Correct 1 ms 1628 KB answer = NO
10 Correct 1 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 1628 KB answer = YES
15 Correct 1 ms 1628 KB answer = YES
16 Correct 1 ms 1628 KB answer = YES
17 Correct 1 ms 1628 KB answer = YES
18 Correct 0 ms 1520 KB answer = YES
19 Incorrect 1 ms 1628 KB Sum of endpoints for edge (1; 1) differs from the expected value 2.
20 Halted 0 ms 0 KB -