| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 870958 |
2023-11-09T15:31:45 Z |
Irate |
Graph (BOI20_graph) |
C++14 |
|
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;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
