oj.uz

답안 #870958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870958 2023-11-09T15:31:45 Z Irate Graph (BOI20_graph) C++14
0 / 100
 2 ms 10072 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB answer = YES
2 Correct 2 ms 10072 KB answer = YES
3 Correct 2 ms 9820 KB answer = YES
4 Correct 2 ms 9944 KB answer = NO
5 Correct 2 ms 10072 KB answer = YES
6 Incorrect 2 ms 9820 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB answer = YES
2 Correct 2 ms 10072 KB answer = YES
3 Correct 2 ms 9820 KB answer = YES
4 Correct 2 ms 9944 KB answer = NO
5 Correct 2 ms 10072 KB answer = YES
6 Incorrect 2 ms 9820 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB answer = YES
2 Correct 2 ms 10072 KB answer = YES
3 Correct 2 ms 9820 KB answer = YES
4 Correct 2 ms 9944 KB answer = NO
5 Correct 2 ms 10072 KB answer = YES
6 Incorrect 2 ms 9820 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB answer = YES
2 Correct 2 ms 10072 KB answer = YES
3 Correct 2 ms 9820 KB answer = YES
4 Correct 2 ms 9944 KB answer = NO
5 Correct 2 ms 10072 KB answer = YES
6 Incorrect 2 ms 9820 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB answer = YES
2 Correct 2 ms 10072 KB answer = YES
3 Correct 2 ms 9820 KB answer = YES
4 Correct 2 ms 9944 KB answer = NO
5 Correct 2 ms 10072 KB answer = YES
6 Incorrect 2 ms 9820 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -