| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1024966 |
2024-07-16T13:24:15 Z |
ach00 |
Graph (BOI20_graph) |
C++14 |
|
2 ms |
2808 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define A first
#define X second
#define EPS 0.00001
int n,m;
vector<ld> ans(100005, numeric_limits<ld>::max());
vector<vector<pair<int,int>>> adj;
vector<pair<int,int>> prelim(100005, {0, 0});
vector<int> arrthing;
ld start_value = numeric_limits<ld>::max();
void explore(int v, int p) {
if(prelim[v].X == 0) {
prelim[v].X = 1;
}
int x = prelim[v].X;
int a = prelim[v].A;
if(a == 0) {
arrthing.push_back(0);
} else if(x == 1) {
arrthing.push_back(-a);
} else {
arrthing.push_back(a);
}
for(auto &e : adj[v]) {
if(start_value != numeric_limits<ld>::max()) return;
int u = e.first;
int c = e.second;
if(u == p) continue;
if(prelim[u].X == 0) {
prelim[u].X = -1*x;
prelim[u].A = c - a;
explore(u, v);
} else {
if(prelim[u].X + x == 0) {
if(prelim[u].A + a != c) {
cout << "NO";
exit(0);
}
}
start_value = ((ld)x)*((ld)(c-a-prelim[u].A))/(2.0);
return;
}
}
}
void assign(int v) {
for(auto &e : adj[v]) {
int u = e.first;
ld c = (ld)e.second;
ld nans = c - ans[v];
if(ans[u] != numeric_limits<ld>::max()) {
if(abs(ans[u] - nans) < EPS) continue;
cout << "NO";
exit(0);
} else {
ans[u] = nans;
assign(u);
}
}
}
int main() {
cin >> n >> m;
ans.resize(n);
adj.resize(n);
for(int i = 0; i < m; i++) {
int a,b,c; cin >> a >> b >> c; a--; b--;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for(int i = 0; i < n; i++) {
if(ans[i] != numeric_limits<ld>::max()) continue;
start_value = numeric_limits<ld>::max();
arrthing = {};
explore(i, -1);
if(start_value != numeric_limits<ld>::max()) {
ans[i] = start_value;
assign(i);
} else {
sort(arrthing.begin(), arrthing.end());
ans[i] = (arrthing.size() != 0) ? ((ld)(arrthing[(arrthing.size())/2] + arrthing[(arrthing.size()-1)/2]))/2.0 : 0;
assign(i);
}
}
cout << "YES\n";
for(int i = 0; i < n; i++) {
cout << ans[i] << ' ';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2796 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2792 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2808 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2796 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2792 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2808 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2796 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2792 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2808 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2796 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2792 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2808 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2796 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2792 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2808 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Incorrect |
1 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
