Submission #958132

#	Time	Username	Problem	Language	Result	Execution time	Memory
958132		kanpham	Graph (BOI20_graph)	C++14	0 / 100	2 ms	4444 KiB

Graph

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define eb emplace_back
#define pb push_back
#define forin(i , a , b) for(int i = (a) ; i <= (b) ; i ++)
#define forint(i , a,  b) for(int i = (a) ; i >= (b) ; i --)
#define fi first
#define se second
#define pii pair<int,int>
#define endl "\n"
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int maxn = 1e5 + 10 ;
int n , m ;
vector <pair<int , long double>> adj[maxn] ;
int cx[maxn] , dx[maxn] , h[maxn] ;
long double gt[maxn];
long double val = 0;
void dfs(int u , int pr)
{
    cx[u] = 1 ;
    for(auto x : adj[u])
    {
        int v = x.fi , w = x.se ;
        if (v == pr) continue ;
        if (cx[v] == 1)
        {
             int kt = abs(h[u] - h[v]) ;
             if (kt % 2 == 0)
            {
                if (h[u] % 2 == 0) val = (w - gt[v] - gt[u]) / 2 ;
                else val = (  (gt[v] + gt[u] - w) / 2 ) ;
            }

            continue ;
        }
        h[v] = h[u] + 1 ;
        gt[v] = w - gt[u] ;
        dfs(v , u) ;
    }

}

void dfs2(int u , int pr)
{
    dx[u] = 1 ;
    for(auto x : adj[u])
    {
        int v = x.fi , w = x.se ;
        if (v == pr ) continue ;
        if (dx[v])
        {
            if (gt[v] + gt[u] != w)
            {
                cout << "NO" ;
                exit(0) ;
            }
            continue ;
        }

        gt[v] = w - gt[u] ;
        dfs2(v , u) ;
    }
}


signed main ()
{
    if(fopen("graph.inp" , "r"))
    {
        freopen("graph.inp" , "r" , stdin) ;
        freopen("graph.out" , "w" , stdout) ;
    }
    fast ;
    cin >> n >> m ;
    forin(i , 1 , m)
    {
        int u , v , w;
        cin >> u >> v >> w;
        adj[u].pb({v , w}) ;
        adj[v].pb({u , w}) ;
    }
    forin(i , 1 , n)
    {
        if (cx[i] == 0)
        {
            gt[i] = 0 ;
            val = -1 ;
            dfs(i , 0) ;
            if (val == -1) val = 0 ;
            //cout << val << endl ;
            gt[i] = val ;
            dfs2(i , 0) ;
        }
    }
    cout << "YES\n" ;
    forin(i , 1 , n) cout << fixed << setprecision(6) <<  gt[i] << " " ;
}

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen("graph.inp" , "r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Graph.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen("graph.out" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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