oj.uz

Submission #230465

# Submission time Handle Problem Language Result Execution time Memory
230465 2020-05-10T07:41:48 Z mehrdad_sohrabi Pipes (BOI13_pipes) C++14
100 / 100
 290 ms 36324 KB 
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
vector <int> g[N];
ll hi[N];
ll ans[N];
map <pii,int> mp;
ll val[N],par[N],vis[N];
ll ras1=0,ras2=0;
ll dfsd(ll v,ll p,ll h){
   // cout << v << " " << p << " " << h << endl;
    par[v]=p;
    hi[v]=h;
    for (auto u : g[v]){
        if (u==p) continue;
        if (hi[u]<hi[v] && hi[u]!=0){
            ras1=v,ras2=u;
        //    cout << v << " " << u << endl;
            continue;
        }
        if (hi[u]!=0) continue;
        dfsd(u,v,h+1);
    }
}
ll dfs(ll v,ll p){
    for (auto u : g[v]){
        if (u==p || vis[u]) continue;
        dfs(u,v);
        val[v]+=-val[u];
        mp[{u,v}]=2*-val[u];
        mp[{v,u}]=mp[{u,v}];
        val[u]=0;
    }
}
vector <pii> yal;
int32_t main(){
    sync;
    ll n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++){
        cin >> val[i];
        val[i]=-val[i];
    }
    for (int i=0;i<m;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        yal.pb({u,v});
    }
    if (m>n) kill(0);
    if (m==n-1){
        dfs(1,1);
        if (val[1]!=0) kill(0);
    }
    if (m==n){
        dfsd(1,1,1);
        vector <int> ras;

        while(ras1!=ras2){
            ras.pb(ras1);
            vis[ras1]=1;
            ras1=par[ras1];
        }
        ras.pb(ras2);
        vis[ras2]=1;
        for (int i=1;i<=n;i++){
            if (vis[i]){
                dfs(i,i);
            }
        }
        ll t=ras.size();
        if (t%2==0) kill(0);
        for (int i=1;i<t;i++){
            ll v=ras[i],u=ras[(i+1)%t];
            val[u]+=-val[v];
            mp[{u,v}]=2*-val[v];
            mp[{v,u}]=2*-val[v];
            val[v]=0;

        }
        ll o=val[ras[0]];
        if (o%2!=0) kill(0);
        o/=2;
        o=-o;
        for (int i=0;i<t;i++){
            ll v=ras[i],u=ras[(i+1)%t];
            if (i%2==0){
                mp[{u,v}]+=2*o;
                mp[{v,u}]+=2*o;
            }
            else{
                mp[{u,v}]-=2*o;
                mp[{v,u}]-=2*o;
            }
        }
    }
    for (pii v : yal){
        cout << mp[v] << endl;
    }
}

Compilation message

pipes.cpp: In function 'll dfsd(ll, ll, ll)':
pipes.cpp:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
pipes.cpp: In function 'll dfs(ll, ll)':
pipes.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 236 ms 25060 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct
11 Correct 8 ms 5248 KB Output is correct
12 Correct 9 ms 5376 KB Output is correct
13 Correct 168 ms 21096 KB Output is correct
14 Correct 203 ms 23908 KB Output is correct
15 Correct 223 ms 25060 KB Output is correct
16 Correct 179 ms 22244 KB Output is correct
17 Correct 221 ms 25076 KB Output is correct
18 Correct 259 ms 25112 KB Output is correct
19 Correct 234 ms 32348 KB Output is correct
20 Correct 7 ms 5120 KB Output is correct
21 Correct 8 ms 5248 KB Output is correct
22 Correct 213 ms 25060 KB Output is correct
23 Correct 177 ms 21380 KB Output is correct
24 Correct 229 ms 25188 KB Output is correct
25 Correct 178 ms 21860 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 9 ms 5376 KB Output is correct
3 Correct 124 ms 22372 KB Output is correct
4 Correct 67 ms 11620 KB Output is correct
5 Correct 63 ms 11748 KB Output is correct
6 Correct 237 ms 28368 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 7 ms 5120 KB Output is correct
14 Correct 8 ms 5120 KB Output is correct
15 Correct 9 ms 5376 KB Output is correct
16 Correct 11 ms 5248 KB Output is correct
17 Correct 8 ms 5248 KB Output is correct
18 Correct 9 ms 5120 KB Output is correct
19 Correct 8 ms 5120 KB Output is correct
20 Correct 8 ms 5120 KB Output is correct
21 Correct 8 ms 5248 KB Output is correct
22 Correct 9 ms 5376 KB Output is correct
23 Correct 214 ms 25984 KB Output is correct
24 Correct 255 ms 30052 KB Output is correct
25 Correct 124 ms 22504 KB Output is correct
26 Correct 67 ms 11624 KB Output is correct
27 Correct 59 ms 11496 KB Output is correct
28 Correct 59 ms 12132 KB Output is correct
29 Correct 213 ms 24272 KB Output is correct
30 Correct 269 ms 34196 KB Output is correct
31 Correct 290 ms 31748 KB Output is correct
32 Correct 243 ms 28260 KB Output is correct
33 Correct 118 ms 22756 KB Output is correct
34 Correct 57 ms 11620 KB Output is correct
35 Correct 63 ms 11752 KB Output is correct
36 Correct 66 ms 11880 KB Output is correct
37 Correct 272 ms 28464 KB Output is correct
38 Correct 259 ms 32228 KB Output is correct
39 Correct 236 ms 27748 KB Output is correct
40 Correct 245 ms 29796 KB Output is correct
41 Correct 92 ms 20324 KB Output is correct
42 Correct 59 ms 11496 KB Output is correct
43 Correct 57 ms 11496 KB Output is correct
44 Correct 56 ms 11748 KB Output is correct
45 Correct 194 ms 25680 KB Output is correct
46 Correct 242 ms 36324 KB Output is correct
47 Correct 254 ms 29924 KB Output is correct
48 Correct 284 ms 31588 KB Output is correct
49 Correct 168 ms 24676 KB Output is correct
50 Correct 59 ms 11752 KB Output is correct
51 Correct 60 ms 11752 KB Output is correct
52 Correct 61 ms 11496 KB Output is correct
53 Correct 185 ms 25808 KB Output is correct
54 Correct 250 ms 33636 KB Output is correct