oj.uz

Submission #958132

# Submission time Handle Problem Language Result Execution time Memory
958132 2024-04-05T02:15:16 Z kanpham Graph (BOI20_graph) C++14
0 / 100
 2 ms 4444 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB answer = YES
2 Correct 2 ms 4444 KB answer = YES
3 Correct 1 ms 4444 KB answer = YES
4 Correct 1 ms 4444 KB answer = NO
5 Correct 2 ms 4444 KB answer = YES
6 Incorrect 2 ms 4444 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB answer = YES
2 Correct 2 ms 4444 KB answer = YES
3 Correct 1 ms 4444 KB answer = YES
4 Correct 1 ms 4444 KB answer = NO
5 Correct 2 ms 4444 KB answer = YES
6 Incorrect 2 ms 4444 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB answer = YES
2 Correct 2 ms 4444 KB answer = YES
3 Correct 1 ms 4444 KB answer = YES
4 Correct 1 ms 4444 KB answer = NO
5 Correct 2 ms 4444 KB answer = YES
6 Incorrect 2 ms 4444 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB answer = YES
2 Correct 2 ms 4444 KB answer = YES
3 Correct 1 ms 4444 KB answer = YES
4 Correct 1 ms 4444 KB answer = NO
5 Correct 2 ms 4444 KB answer = YES
6 Incorrect 2 ms 4444 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB answer = YES
2 Correct 2 ms 4444 KB answer = YES
3 Correct 1 ms 4444 KB answer = YES
4 Correct 1 ms 4444 KB answer = NO
5 Correct 2 ms 4444 KB answer = YES
6 Incorrect 2 ms 4444 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -