Submission #1040028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040028		goodspeed0208	Graph (BOI20_graph)	C++14	58 / 100	1022 ms	25800 KiB

Graph

#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 (stderr)

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 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 42