| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 915229 |
2024-01-23T14:27:31 Z |
Amr |
Graph (BOI20_graph) |
C++14 |
|
3 ms |
10856 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
ll res = 1;
x = x; // % mod;
if (x == 0) return 0;
while (y > 0)
{
if (y & 1) res = (res*x) ; // % mod;
y = y>>1;
x = (x*x) ; // % mod;
}
return res;
}
double ans[N]; // -1e18
ll dep[N];
ll cur[N];
ll vis[N];
ll vis2[N];
vector<pair<ll,ll> > v[N];
bool is_yes = 1;
ll n , m, anyone=-1;
ll sum = 0;
void dfs1(ll x,ll dis, ll par)
{
if(vis[x])
{
if(dep[x]>dep[par]) return;
ll c = cur[par] + cur[x];
if((dep[par]-dep[x])%2==1)
{
if(dis!=c)is_yes = 0;
}
else
{
if(ans[x]==-1e18) ans[x] = (dis-c)/2.0, anyone = x;
else if((dis-c)/2.0!=ans[x]) is_yes = 0;
}
return;
}
if(par!=0) cur[x] = dis-cur[par];
dep[x] = dep[par]+1;
vis[x] = 1;
for(pair<ll,ll> newn: v[x])
{
if(newn.F!=par) dfs1(newn.F,newn.S,x);
}
}
ll cursum = 0;
vector<ll> vec;
void dfs2(ll x, ll dis, ll par)
{
if(vis2[x])
{
if(dep[x]>dep[par]) return;
if(ans[x]!=-1e18) if(ans[x]!=(dis-ans[par])) is_yes = 0;
else ans[x] = (dis-ans[par]);
return;
}
vec.push_back(x);
if(par!=0){
if(ans[x]!=-1e18) {if(ans[x]!=(dis-ans[par])) is_yes = 0;}
else ans[x] = (dis-ans[par]);}
cursum+=abs(ans[x]);
vis2[x] = 1;
for(pair<ll,ll> newn: v[x])
{
if(newn.F != par) dfs2(newn.F,newn.S,x);
}
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) ans[i] = -1e18;
for(int i = 0; i < m; i++)
{
ll x, y, z; cin >> x >> y >> z;
v[x].push_back({y,z});
v[y].push_back({x,z});
}
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
dfs1(i,0,0);
//for(int i = 1; i <= n ;i++) cout << ans[i] << " "; cout << endl;
if(is_yes==0) {No; return;}
if(anyone!=-1) dfs2(anyone,0,0);
else
{
ll mncursum = 1e18,cntcursum;
for(int l = -10*n; l <= 10*n; l++)
{cursum = 0; vec.clear();
ans[1] = l; dfs2(1,0,0);
for(int j = 0; j < vec.sz; j++) vis2[vec[j]] = 0,ans[vec[j]]=-1e18;
if(cursum<mncursum)
{
mncursum = cursum;
cntcursum = l;
}
}
ans[1] = cntcursum;
//cout << cntcursum << endl;
dfs2(1,0,0);
}
if(is_yes==0) {No; return;}
}
}
Yes;
for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
}
int main(){
//freopen("friday.in","r",stdin);
//freopen("friday.out","w",stdout);
fast;
//cin >> TT;
while(TT--)
solve();
return 0;
}
Compilation message
Graph.cpp: In function 'void dfs2(ll, ll, ll)':
Graph.cpp:74:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
74 | if(ans[x]!=-1e18) if(ans[x]!=(dis-ans[par])) is_yes = 0;
| ^
Graph.cpp: In function 'void solve()':
Graph.cpp:117:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int j = 0; j < vec.sz; j++) vis2[vec[j]] = 0,ans[vec[j]]=-1e18;
| ^
Graph.cpp:132:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
132 | for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
| ^~~
Graph.cpp:132:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
132 | for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
| ^~~~
Graph.cpp:124:24: warning: 'cntcursum' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | ans[1] = cntcursum;
| ~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
answer = YES |
| 2 |
Correct |
3 ms |
10856 KB |
answer = YES |
| 3 |
Correct |
3 ms |
10844 KB |
answer = YES |
| 4 |
Correct |
2 ms |
10844 KB |
answer = NO |
| 5 |
Incorrect |
3 ms |
10844 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
answer = YES |
| 2 |
Correct |
3 ms |
10856 KB |
answer = YES |
| 3 |
Correct |
3 ms |
10844 KB |
answer = YES |
| 4 |
Correct |
2 ms |
10844 KB |
answer = NO |
| 5 |
Incorrect |
3 ms |
10844 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
answer = YES |
| 2 |
Correct |
3 ms |
10856 KB |
answer = YES |
| 3 |
Correct |
3 ms |
10844 KB |
answer = YES |
| 4 |
Correct |
2 ms |
10844 KB |
answer = NO |
| 5 |
Incorrect |
3 ms |
10844 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
answer = YES |
| 2 |
Correct |
3 ms |
10856 KB |
answer = YES |
| 3 |
Correct |
3 ms |
10844 KB |
answer = YES |
| 4 |
Correct |
2 ms |
10844 KB |
answer = NO |
| 5 |
Incorrect |
3 ms |
10844 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
answer = YES |
| 2 |
Correct |
3 ms |
10856 KB |
answer = YES |
| 3 |
Correct |
3 ms |
10844 KB |
answer = YES |
| 4 |
Correct |
2 ms |
10844 KB |
answer = NO |
| 5 |
Incorrect |
3 ms |
10844 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 6 |
Halted |
0 ms |
0 KB |
- |
