제출 #1312250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312250		vlomaczk	Graph (BOI20_graph)	C++20	100 / 100	96 ms	25428 KiB

Graph

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 200'010;
vector<int> vis(M);
vector<pair<int, int>> X(M);
vector<vector<pair<int, int>>> g(M);

set<ld> cands;
vector<int> S;

pair<int, int> gen(pair<int, int> org, int w) {
	return {-org.first, w - org.second};
}

int can_solve(pair<int, int> x, pair<int, int> y) { //0 - sprzecznosc 1 - tozsamosciowe, 2 - solve
	auto[a,b] = x;
	auto[c,d] = y;
	if(a==c) {
		if(d==b) return 1;
		return 0;
	}
	return 2;
}

ld solve(pair<int, int> x, pair<int, int> y) {
	auto[a,b] = x;
	auto[c,d] = y;
	return (ld)(d-b) / (a-c);
}

void dfs(int v) {
	if(vis[v]) return;
	S.push_back(v);
	vis[v] = 1;
	for(auto[u,w] : g[v]) {
		if(!vis[u]) {
			X[u] = gen(X[v], w);
		} else {
			int c = can_solve(X[v], gen(X[u], w));
			if(c==0) {
				cands.insert(-1);
				cands.insert(0);
			} else if(c==2) {
				cands.insert(solve(X[v], gen(X[u], w))); 
			}
		}
		dfs(u);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;
	for(int i=0; i<m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	vector<ld> ans(n+1);
	for(int r=1; r<=n; ++r) {
		if(vis[r]) continue;
		X[r] = {1,0};
		dfs(r);
		if(cands.size() > 1) {
			cout << "NO\n";
			return 0;
		}  else if(cands.size()==1) {
			ld x = *cands.begin();
			for(auto v : S) {
				ans[v] = x*X[v].first + X[v].second;
			}
		} else {
			ll sum = -1;
			ld x = 1;
			pair<ll, ll> curr_val = {0,0};
			map<int, int> dod, uj;
			vector<pair<ll, ll>> sweep;
			for(auto v : S) {
				auto[a,b] = X[v];
				if(a > 0) {
					dod[b]++;
					curr_val.first--;
					curr_val.second-=b;
				} else {
					uj[b]++;
					curr_val.first--;
					curr_val.second+=b;
				}
			}
			for(auto[a,b] : dod) sweep.push_back({-a, 1});
			for(auto[a,b] : uj) sweep.push_back({a, -1});
			sort(sweep.begin(), sweep.end());
			for(auto[poz, typ] : sweep) {
				ll curr_sum = poz * curr_val.first + curr_val.second;
				if(sum==-1 || curr_sum < sum) {
					sum = curr_sum;
					x = poz;
				}
				if(typ==1) {
					curr_val.first += 2 * dod[-poz];
					curr_val.second += 2 * (-poz) * dod[-poz];
				} else {
					curr_val.first += 2 * uj[poz];
					curr_val.second -= 2 * poz * uj[poz];
				}
			}
			for(auto v : S) ans[v] = x*X[v].first + X[v].second;
		}
		while(cands.size()) cands.erase(*cands.begin());
		while(S.size()) S.pop_back();
	}
	cout << "YES\n";
	for(int i=1; i<=n; ++i) cout << fixed << setprecision(1) << ans[i] << " "; cout << "\n";
 
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 42 / 42
• Subtask 5: 5 / 5