Submission #915220

#	Time	Username	Problem	Language	Result	Execution time	Memory
915220		Amr	Graph (BOI20_graph)	C++14	0 / 100	3 ms	10844 KiB

Graph

#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);
    }
}
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;
    }
    if(par!=0){
    if(ans[x]!=-1e18) {if(ans[x]!=(dis-ans[par])) is_yes = 0;}
    else ans[x] = (dis-ans[par]);}
    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
            {
                ans[1] = 0;
                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 (stderr)

Graph.cpp: In function 'void dfs2(ll, ll, ll)':
Graph.cpp:72:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   72 |         if(ans[x]!=-1e18) if(ans[x]!=(dis-ans[par])) is_yes = 0;
      |           ^
Graph.cpp: In function 'void solve()':
Graph.cpp:113:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  113 |     for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
      |     ^~~
Graph.cpp:113:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  113 |     for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
      |                                                        ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42