oj.uz

Submission #31304

# Submission time Handle Problem Language Result Execution time Memory
31304 2017-08-17T23:39:10 Z imaxblue Pipes (BOI13_pipes) C++14
0 / 100
 659 ms 23404 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(zqfmgb, x) for (int zqfmgb=0; zqfmgb<x; ++zqfmgb)
#define fox1(zqfmgb, x) for (int zqfmgb=1; zqfmgb<=x; ++zqfmgb)
#define foxr(zqfmgb, x) for (int zqfmgb=x-1; zqfmgb>=0; --zqfmgb)
#define fox1r(zqfmgb, x) for (int zqfmgb=x; zqfmgb>0; --zqfmgb)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)

int n, m, a, b, N, C;
ll c[100005], f[500005], k;
int in[100005];
bool u[100005];
vector<pii> v[100005], s;
queue<int> q;
void dfs(int N, int P){
    //cout << N << ' ' << C << endl;
    if (u[N]){
        //cout << "*" << endl;
        if (u[N]==C){
            cout << 0 << endl;
            exit(0);
        }
        if (in[N]==-1) return;
        s.pb(mp(N, -1));
        fox(l, s.size()-1){
            in[s[l].x]=-1;
            c[s[l+1].x]-=c[s[l].x];
            f[s[l].y]+=c[s[l].x];
            //cout << s[l].y << ' ' << f[s[l].y] << endl;
        }
        k=c[s[0].x]/2;
        fox(l, s.size()-1){
            f[s[l].y]+=k;
            k*=-1;
        }
        s.pop_back();
        return;
    }

    u[N]=C;
    fox(l, v[N].size()){
        if (in[v[N][l].x]==0 || v[N][l].x==P) continue;
        C=3-C;
        s.pb(mp(N, v[N][l].y));
        dfs(v[N][l].x, N);
        s.pop_back();
        C=3-C;
    }
}
int main(){
    cin >> n >> m;

    fox1(l, n) cin >> c[l];
    fox(l, m){
        cin >> a >> b;
        v[a].pb(mp(b, l));
        v[b].pb(mp(a, l));
        in[a]++; in[b]++;
    }
    fox1(l, n){
        if (in[l]==1) q.push(l);
    }
    /*while(!q.empty()){
        N=q.front(); q.pop();
        if (in[N]!=1) continue;
        in[N]--;
        fox(l, v[N].size()){
            if (in[v[N][l].x]==0) continue;
            c[v[N][l].x]-=c[N];
            f[v[N][l].y]=c[N];
            //cout << N << ' ' << v[N][l].y << ' ' << c[N] << endl;
            in[v[N][l].x]--;
            if (in[v[N][l].x]==1) q.push(v[N][l].x);
        }
    }
    fox1(l, n){
        if (in[l]==0 || u[l]) continue;
        C=1;
        dfs(l, -1);
    }*/
    for (int l=0; l<m; ++l){
        f[l]*=2;
        cout << f[l] << endl;
    }
    return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:18:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(zqfmgb, x) for (int zqfmgb=0; zqfmgb<x; ++zqfmgb)
                                                 ^
pipes.cpp:42:9: note: in expansion of macro 'fox'
         fox(l, s.size()-1){
         ^
pipes.cpp:18:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(zqfmgb, x) for (int zqfmgb=0; zqfmgb<x; ++zqfmgb)
                                                 ^
pipes.cpp:49:9: note: in expansion of macro 'fox'
         fox(l, s.size()-1){
         ^
pipes.cpp:18:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(zqfmgb, x) for (int zqfmgb=0; zqfmgb<x; ++zqfmgb)
                                                 ^
pipes.cpp:58:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9544 KB Output isn't correct
2 Incorrect 0 ms 9544 KB Output isn't correct
3 Incorrect 0 ms 9544 KB Output isn't correct
4 Incorrect 206 ms 13504 KB Output isn't correct
5 Incorrect 3 ms 9544 KB Output isn't correct
6 Incorrect 0 ms 9544 KB Output isn't correct
7 Incorrect 3 ms 9544 KB Output isn't correct
8 Incorrect 3 ms 9544 KB Output isn't correct
9 Incorrect 3 ms 9544 KB Output isn't correct
10 Incorrect 0 ms 9544 KB Output isn't correct
11 Incorrect 6 ms 9544 KB Output isn't correct
12 Incorrect 0 ms 9544 KB Output isn't correct
13 Incorrect 153 ms 12712 KB Output isn't correct
14 Runtime error 249 ms 13240 KB Execution timed out (wall clock limit exceeded)
15 Runtime error 216 ms 13504 KB Execution timed out (wall clock limit exceeded)
16 Runtime error 173 ms 12844 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 159 ms 13504 KB Execution timed out (wall clock limit exceeded)
18 Incorrect 253 ms 13504 KB Output isn't correct
19 Runtime error 186 ms 12712 KB Execution timed out (wall clock limit exceeded)
20 Incorrect 0 ms 9544 KB Output isn't correct
21 Incorrect 6 ms 9544 KB Output isn't correct
22 Runtime error 206 ms 13504 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 159 ms 12712 KB Execution timed out (wall clock limit exceeded)
24 Incorrect 206 ms 13504 KB Output isn't correct
25 Runtime error 173 ms 12848 KB Execution timed out (wall clock limit exceeded)

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9544 KB Output isn't correct
2 Incorrect 0 ms 9544 KB Output isn't correct
3 Runtime error 209 ms 12976 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 246 ms 12844 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 253 ms 13240 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 583 ms 23404 KB Execution timed out (wall clock limit exceeded)
7 Incorrect 3 ms 9544 KB Output isn't correct
8 Incorrect 0 ms 9544 KB Output isn't correct
9 Incorrect 3 ms 9544 KB Output isn't correct
10 Incorrect 0 ms 9544 KB Output isn't correct
11 Incorrect 0 ms 9544 KB Output isn't correct
12 Incorrect 3 ms 9544 KB Output isn't correct
13 Incorrect 0 ms 9544 KB Output isn't correct
14 Incorrect 0 ms 9544 KB Output isn't correct
15 Incorrect 0 ms 9544 KB Output isn't correct
16 Incorrect 3 ms 9544 KB Output isn't correct
17 Incorrect 9 ms 9544 KB Output isn't correct
18 Incorrect 6 ms 9544 KB Output isn't correct
19 Incorrect 6 ms 9544 KB Output isn't correct
20 Incorrect 0 ms 9544 KB Output isn't correct
21 Incorrect 3 ms 9676 KB Output isn't correct
22 Incorrect 9 ms 9544 KB Output isn't correct
23 Runtime error 169 ms 12316 KB Execution timed out (wall clock limit exceeded)
24 Incorrect 173 ms 13108 KB Output isn't correct
25 Runtime error 183 ms 12976 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 219 ms 12976 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 189 ms 12712 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 199 ms 13376 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 556 ms 20764 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 236 ms 12712 KB Execution timed out (wall clock limit exceeded)
31 Incorrect 236 ms 12844 KB Output isn't correct
32 Runtime error 209 ms 13372 KB Execution timed out (wall clock limit exceeded)
33 Incorrect 249 ms 13108 KB Output isn't correct
34 Runtime error 269 ms 12844 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 179 ms 12844 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 243 ms 13240 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 659 ms 23404 KB Execution timed out (wall clock limit exceeded)
38 Incorrect 226 ms 12844 KB Output isn't correct
39 Runtime error 219 ms 13372 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 216 ms 13108 KB Execution timed out (wall clock limit exceeded)
41 Incorrect 253 ms 12844 KB Output isn't correct
42 Runtime error 229 ms 12712 KB Execution timed out (wall clock limit exceeded)
43 Runtime error 223 ms 12712 KB Execution timed out (wall clock limit exceeded)
44 Runtime error 196 ms 13240 KB Execution timed out (wall clock limit exceeded)
45 Runtime error 603 ms 21820 KB Execution timed out (wall clock limit exceeded)
46 Runtime error 219 ms 12712 KB Execution timed out (wall clock limit exceeded)
47 Runtime error 196 ms 13108 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 186 ms 12844 KB Execution timed out (wall clock limit exceeded)
49 Runtime error 209 ms 13240 KB Execution timed out (wall clock limit exceeded)
50 Runtime error 236 ms 12976 KB Execution timed out (wall clock limit exceeded)
51 Runtime error 206 ms 13108 KB Execution timed out (wall clock limit exceeded)
52 Incorrect 213 ms 12844 KB Output isn't correct
53 Runtime error 593 ms 21556 KB Execution timed out (wall clock limit exceeded)
54 Runtime error 216 ms 12844 KB Execution timed out (wall clock limit exceeded)