Submission #870958

#	Time	Username	Problem	Language	Result	Execution time	Memory
870958		Irate	Graph (BOI20_graph)	C++14	0 / 100	2 ms	10072 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 5;
bool vis[mxN];
vector<pair<int, int>> nodes[mxN];
vector<pair<int, int>> G[mxN];
set<double> evaluate[mxN];
int cycle = -1;
void dfs(int node, int par){
	vis[node] = 1;
	for(pair<int, int> &v : G[node]){
		int to = v.first, color = v.second;
		if(to == par)continue;
		nodes[to].push_back({-nodes[node][0].first, color - nodes[node][0].second});
		if(nodes[to].size() >= 2)cycle = to;
		if(!vis[to])dfs(to, node);
	}
}
void Calc(int node, int par, double X){
	vis[node] = 1;
	for(pair<int, int> &v : G[node]){
		int to = v.first, color = v.second;
		if(to == par)continue;
		evaluate[to].insert(X * nodes[to][0].first + nodes[to][0].second);
		if(!vis[to])Calc(to, node, X);
	}
}
vector<int>cnter;
void cnt(int node, int par){
	cnter.push_back(nodes[node][0].second);
	for(pair<int, int> &v : G[node]){
		int to = v.first;
		if(to != par)cnt(to, node);
	}
}
struct T{
	int u, v, color;
};
T edges[2 * mxN];
int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 0;i < m;++i){
		int u, v, color;
		cin >> u >> v >> color;
		G[u].push_back({v, color});
		G[v].push_back({u, color});
		edges[i].u = u;
		edges[i].v = v;
		edges[i].color = color;
	}
	vector<double>comps(n + 1);
	for(int i = 1;i <= n;++i){
		if(!vis[i]){
			nodes[i].push_back({1, 0});
			dfs(i, i);
			if(cycle != -1)comps[i] = (1.0 * nodes[cycle][1].second - nodes[cycle][0].second) / (nodes[cycle][0].first - nodes[cycle][1].first);
			else comps[i] = 1e9; // tree
			cycle = -1;
		}
	}
	for(int i = 1;i <= n;++i)vis[i] = 0;
	for(int i = 1;i <= n;++i){
		if(comps[i] && comps[i] != 1e9){
			evaluate[i].insert(comps[i] * nodes[i][0].first + nodes[i][0].second);
			Calc(i, i, comps[i]);
		}
	}
	for(int i = 1;i <= n;++i){
		if(comps[i] == 1e9){
			cnt(i, i);
			sort(cnter.begin(), cnter.end());
			double x;
			if(cnter.size() % 2){
				x = cnter[cnter.size() / 2];
			}
			else{
				x = (cnter[cnter.size() / 2 - 1] + cnter[cnter.size() / 2]) / 2.0; 
			}
			evaluate[i].insert(x);
			Calc(i, i, x);
			cnter.clear();
		}
	}
	for(int i = 1;i <= n;++i){
		if(evaluate[i].size() >= 2){
			cout << "NO";
			return 0;
		}
	}
	for(int i = 0;i < m;++i){
		int u = edges[i].u, v = edges[i].v, color = edges[i].color;
		if(*evaluate[u].begin() + *evaluate[v].begin() != color){
			cout << "NO";
			return 0;
		}
	}
	cout << "YES\n";
	for(int i = 1;i <= n;++i){
		cout << *evaluate[i].begin() << ' ';
	}
}	
/*
5 4                                                                                                                                                  
1 2 2                                                                                                                                                
1 3 1                                                                                                                                                
2 4 1                                                                                                                                                
4 5 2
*/

Compilation message (stderr)

Graph.cpp: In function 'void Calc(int, int, double)':
Graph.cpp:22:21: warning: unused variable 'color' [-Wunused-variable]
   22 |   int to = v.first, color = v.second;
      |                     ^~~~~

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