Submission #581677

#	Time	Username	Problem	Language	Result	Execution time	Memory
581677		elpro123	Graph (BOI20_graph)	C++14	100 / 100	261 ms	17768 KiB

Graph

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
int N, M, vistos[100005], datos[100005], con[100005];
double val[100005];
vector<pii> graph[100005];
vector<int> nds, elems;
int founda = 0, rip = 0;
double aval = 0;
 
void ripexit() {
	printf("NO\n");
	
}
 
void dfs(int x) {
	nds.push_back(x);
	vistos[x] = 1;
	for(pii p : graph[x]){
		int v = p.first, k = p.second;
		if(vistos[v]){
			if(datos[v] + datos[x]){
				double pval = (k - (con[v] + con[x]))/((double)(datos[v] + datos[x]));
				if(founda){ 
					if(abs(pval - aval) > 0) {//0.0000001
						rip = 1;
					}
				}else{
					founda = 1;
					aval = pval;
				}
			}else{
				if(con[v] + con[x] != k){
					rip = 1;
				}
			}
		}else{
			datos[v] = -datos[x];
			con[v] = k - con[x];
			dfs(v);
		}
	}
}
 
int main() {
	cin>>N>>M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}
	for (int i = 1; i <= N; i++) {
		if (!vistos[i]) {
			founda = 0, rip = 0;
			datos[i] = 1;
			con[i] = 0;
			dfs(i);
			if (rip) {
				ripexit();
				return 0;
			}
			if (!founda) {
				elems.clear();
				for(int x : nds) {
					elems.push_back(con[x] * datos[x]);
				}
				sort(elems.begin(), elems.end());
				aval = -elems[elems.size()/2];
			}
			for (int x : nds) {
				val[x] = datos[x] * aval + con[x];
			}
			nds.clear();
		}
	}
	puts("YES");
	for(int i=1; i<=N; i++) {
		if(i == 1){
			cout<<val[i]<<" ";
		}else{
			cout<<val[i]<<" ";
		}
	} 
	cout<<"\n";
}

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