Submission #31302

# Submission time Handle Problem Language Result Execution time Memory
31302 2017-08-17T23:31:18 Z imaxblue Pipes (BOI13_pipes) C++14
35 / 100
606 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(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#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:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
pipes.cpp:42:9: note: in expansion of macro 'fox'
         fox(l, s.size()-1){
         ^
pipes.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
pipes.cpp:49:9: note: in expansion of macro 'fox'
         fox(l, s.size()-1){
         ^
pipes.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
pipes.cpp:58:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^
pipes.cpp: In function 'int main()':
pipes.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
pipes.cpp:83:9: note: in expansion of macro 'fox'
         fox(l, v[N].size()){
         ^
# 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 3 ms 9544 KB Output isn't correct
4 Incorrect 159 ms 13504 KB Output isn't correct
5 Incorrect 0 ms 9544 KB Output isn't correct
6 Incorrect 0 ms 9544 KB Output isn't correct
7 Incorrect 0 ms 9544 KB Output isn't correct
8 Incorrect 0 ms 9544 KB Output isn't correct
9 Incorrect 0 ms 9544 KB Output isn't correct
10 Incorrect 0 ms 9544 KB Output isn't correct
11 Incorrect 3 ms 9544 KB Output isn't correct
12 Incorrect 0 ms 9544 KB Output isn't correct
13 Incorrect 99 ms 12712 KB Output isn't correct
14 Incorrect 166 ms 13240 KB Output isn't correct
15 Incorrect 156 ms 13504 KB Output isn't correct
16 Incorrect 163 ms 12844 KB Output isn't correct
17 Incorrect 166 ms 13504 KB Output isn't correct
18 Incorrect 149 ms 13504 KB Output isn't correct
19 Incorrect 166 ms 12712 KB Output isn't correct
20 Incorrect 0 ms 9544 KB Output isn't correct
21 Incorrect 0 ms 9544 KB Output isn't correct
22 Incorrect 153 ms 13504 KB Output isn't correct
23 Incorrect 136 ms 12712 KB Output isn't correct
24 Incorrect 156 ms 13504 KB Output isn't correct
25 Incorrect 133 ms 12848 KB Output isn't correct
# 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 Correct 159 ms 17580 KB Output is correct
4 Incorrect 183 ms 20888 KB Output isn't correct
5 Correct 149 ms 13240 KB Output is correct
6 Correct 599 ms 23404 KB Output is correct
7 Incorrect 0 ms 9544 KB Output isn't correct
8 Incorrect 0 ms 9544 KB Output isn't correct
9 Correct 0 ms 9544 KB Output is correct
10 Incorrect 0 ms 9544 KB Output isn't correct
11 Incorrect 0 ms 9544 KB Output isn't correct
12 Correct 0 ms 9544 KB Output is correct
13 Correct 0 ms 9544 KB Output is correct
14 Incorrect 0 ms 9544 KB Output isn't correct
15 Incorrect 3 ms 9544 KB Output isn't correct
16 Incorrect 0 ms 9544 KB Output isn't correct
17 Correct 0 ms 9544 KB Output is correct
18 Incorrect 0 ms 9544 KB Output isn't correct
19 Incorrect 0 ms 9544 KB Output isn't correct
20 Correct 3 ms 9544 KB Output is correct
21 Correct 0 ms 9676 KB Output is correct
22 Incorrect 3 ms 9544 KB Output isn't correct
23 Incorrect 126 ms 17660 KB Output isn't correct
24 Incorrect 199 ms 18416 KB Output isn't correct
25 Correct 139 ms 17580 KB Output is correct
26 Correct 176 ms 18844 KB Output is correct
27 Correct 159 ms 15888 KB Output is correct
28 Correct 153 ms 13376 KB Output is correct
29 Correct 486 ms 20764 KB Output is correct
30 Incorrect 156 ms 17348 KB Output isn't correct
31 Incorrect 159 ms 21904 KB Output isn't correct
32 Incorrect 146 ms 15168 KB Output isn't correct
33 Correct 176 ms 18620 KB Output is correct
34 Correct 139 ms 18668 KB Output is correct
35 Incorrect 166 ms 20892 KB Output isn't correct
36 Correct 149 ms 13240 KB Output is correct
37 Correct 606 ms 23404 KB Output is correct
38 Incorrect 153 ms 17640 KB Output isn't correct
39 Incorrect 146 ms 14368 KB Output isn't correct
40 Incorrect 179 ms 17988 KB Output isn't correct
41 Correct 173 ms 21908 KB Output is correct
42 Correct 179 ms 19076 KB Output is correct
43 Correct 163 ms 21384 KB Output is correct
44 Correct 143 ms 13240 KB Output is correct
45 Correct 503 ms 21820 KB Output is correct
46 Incorrect 183 ms 16964 KB Output isn't correct
47 Incorrect 179 ms 18124 KB Output isn't correct
48 Incorrect 163 ms 21640 KB Output isn't correct
49 Correct 129 ms 14548 KB Output is correct
50 Incorrect 153 ms 18728 KB Output isn't correct
51 Correct 146 ms 17420 KB Output is correct
52 Correct 156 ms 14268 KB Output is correct
53 Correct 503 ms 21556 KB Output is correct
54 Incorrect 166 ms 16772 KB Output isn't correct