| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1030508 |
2024-07-22T06:12:16 Z |
12345678 |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2816 KB |
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int n, m, u, v, w, a[nx], b[nx], f, vs[nx];
double res[nx];
vector<pair<int, int>> d[nx];
vector<int> comp;
set<double> s;
void dfs(int u, int p)
{
vs[u]=1;
comp.push_back(u);
for (auto [v, w]:d[u])
{
if (v==p) continue;
if (vs[v])
{
int sma=a[u]+a[v], smb=b[u]+b[v];
if (a[u]+a[v]==0&&b[u]+b[v]==w) continue;
smb=w-smb;
s.insert(((double)smb)/((double)sma));
}
else
{
a[v]=-a[u];
b[v]=w-b[u];
dfs(v, u);
}
}
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
for (int i=1; i<=n; i++)
{
if (!vs[i])
{
comp.clear();
s.clear();
a[i]=1;
dfs(i, i);
if (s.size()>1) f=1;
else if (s.size()==1)
{
double vl=*s.begin();
for (auto x:comp) res[x]=a[x]*vl+b[x];
}
else
{
double x;
vector<double> v;
for (auto x:comp) v.push_back((double)(-b[x])/(double)a[x]);
sort(v.begin(), v.end());
pair<double, double> mn={DBL_MAX, 0};
for (auto k:v)
{
double tmp=0;
for (auto x:comp) tmp+=abs(a[x]*k+b[x]);
mn=min(mn, {tmp, k});
}
for (auto x:comp) res[x]=mn.second*a[x]+b[x];
}
}
}
if (f) return cout<<"NO\n", 0;
cout<<"YES\n";
for (int i=1; i<=n; i++) cout<<setprecision(8)<<res[i]<<' ';
}
Compilation message
Graph.cpp: In function 'int main()':
Graph.cpp:56:24: warning: unused variable 'x' [-Wunused-variable]
56 | double x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2816 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 9 |
Incorrect |
1 ms |
2652 KB |
Expected double, but "-inf" found |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2816 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 9 |
Incorrect |
1 ms |
2652 KB |
Expected double, but "-inf" found |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2816 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 9 |
Incorrect |
1 ms |
2652 KB |
Expected double, but "-inf" found |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2816 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 9 |
Incorrect |
1 ms |
2652 KB |
Expected double, but "-inf" found |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2652 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Correct |
1 ms |
2816 KB |
answer = YES |
| 7 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 8 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 9 |
Incorrect |
1 ms |
2652 KB |
Expected double, but "-inf" found |
| 10 |
Halted |
0 ms |
0 KB |
- |
