| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1030559 |
2024-07-22T06:51:57 Z |
12345678 |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2820 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<tuple<int, 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, idx]:d[u])
{
if (idx==p) continue;
if (vs[v])
{
int sma=a[u]+a[v], smb=b[u]+b[v];
if (sma==0&&b[u]+b[v]==w) continue;
else if (sma==0&&b[u]+b[v]!=w)
{
f=1;
break;
}
s.insert(((double)(w-smb))/((double)sma));
}
else
{
a[v]=-a[u];
b[v]=w-b[u];
dfs(v, idx);
}
}
}
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, i}), d[v].push_back({u, w, i});
for (int i=1; i<=n; i++)
{
if (!vs[i])
{
comp.clear();
s.clear();
a[i]=1;
dfs(i, -1);
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
{
vector<pair<double, int>> v;
for (auto x:comp) if (a[x]!=0) v.push_back({(double)(-b[x])/(double)a[x], x});
sort(v.begin(), v.end());
vector<int> qs(v.size());
for (int i=0; i<v.size(); i++)
{
qs[i]=abs(a[v[i].second]);
if (i!=0) qs[i]+=qs[i-1];
}
int t=qs[v.size()-1]/2;
int idx=lower_bound(qs.begin(), qs.end(), t)-qs.begin();
for (auto x:comp) res[x]=v[idx].first*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:64:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i=0; i<v.size(); i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2820 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2820 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2820 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2820 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2820 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2652 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
