Submission #31300

# Submission time Handle Problem Language Result Execution time Memory
31300 2017-08-17T23:26:31 Z imaxblue Pipes (BOI13_pipes) C++14
53 / 100
693 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){
        cout << f[l]*2 << 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 Correct 0 ms 9544 KB Output is correct
2 Correct 0 ms 9544 KB Output is correct
3 Correct 3 ms 9544 KB Output is correct
4 Correct 239 ms 13504 KB Output is correct
5 Correct 3 ms 9544 KB Output is correct
6 Correct 3 ms 9544 KB Output is correct
7 Correct 0 ms 9544 KB Output is correct
8 Correct 0 ms 9544 KB Output is correct
9 Correct 6 ms 9544 KB Output is correct
10 Correct 0 ms 9544 KB Output is correct
11 Correct 3 ms 9544 KB Output is correct
12 Correct 3 ms 9544 KB Output is correct
13 Runtime error 219 ms 12712 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 203 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 193 ms 12844 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 226 ms 13504 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 223 ms 13504 KB Execution timed out (wall clock limit exceeded)
19 Runtime error 283 ms 12712 KB Execution timed out (wall clock limit exceeded)
20 Correct 0 ms 9544 KB Output is correct
21 Correct 6 ms 9544 KB Output is correct
22 Runtime error 206 ms 13504 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 163 ms 12712 KB Execution timed out (wall clock limit exceeded)
24 Correct 283 ms 13504 KB Output is correct
25 Runtime error 169 ms 12848 KB Execution timed out (wall clock limit exceeded)
# 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 146 ms 17576 KB Output is correct
4 Runtime error 219 ms 20892 KB Execution timed out (wall clock limit exceeded)
5 Correct 149 ms 13240 KB Output is correct
6 Correct 693 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 3 ms 9544 KB Output isn't correct
12 Correct 0 ms 9544 KB Output is correct
13 Correct 3 ms 9544 KB Output is correct
14 Incorrect 3 ms 9544 KB Output isn't correct
15 Incorrect 3 ms 9544 KB Output isn't correct
16 Incorrect 9 ms 9544 KB Output isn't correct
17 Correct 3 ms 9544 KB Output is correct
18 Incorrect 9 ms 9544 KB Output isn't correct
19 Incorrect 3 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 Runtime error 223 ms 17668 KB Execution timed out (wall clock limit exceeded)
24 Incorrect 273 ms 18412 KB Output isn't correct
25 Correct 169 ms 17576 KB Output is correct
26 Correct 166 ms 18848 KB Output is correct
27 Correct 159 ms 15892 KB Output is correct
28 Correct 146 ms 13376 KB Output is correct
29 Correct 429 ms 20764 KB Output is correct
30 Runtime error 246 ms 17344 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 266 ms 21908 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 216 ms 15168 KB Execution timed out (wall clock limit exceeded)
33 Correct 173 ms 18620 KB Output is correct
34 Correct 159 ms 18672 KB Output is correct
35 Runtime error 276 ms 20892 KB Execution timed out (wall clock limit exceeded)
36 Correct 143 ms 13240 KB Output is correct
37 Correct 646 ms 23404 KB Output is correct
38 Runtime error 206 ms 17644 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 213 ms 14368 KB Execution timed out (wall clock limit exceeded)
40 Incorrect 246 ms 17988 KB Output isn't correct
41 Correct 176 ms 21908 KB Output is correct
42 Correct 156 ms 19072 KB Output is correct
43 Correct 146 ms 21380 KB Output is correct
44 Correct 146 ms 13240 KB Output is correct
45 Correct 483 ms 21820 KB Output is correct
46 Runtime error 199 ms 16964 KB Execution timed out (wall clock limit exceeded)
47 Runtime error 239 ms 18120 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 246 ms 21648 KB Execution timed out (wall clock limit exceeded)
49 Correct 149 ms 14544 KB Output is correct
50 Runtime error 236 ms 18724 KB Execution timed out (wall clock limit exceeded)
51 Correct 153 ms 17420 KB Output is correct
52 Correct 163 ms 14260 KB Output is correct
53 Correct 476 ms 21556 KB Output is correct
54 Incorrect 289 ms 16768 KB Output isn't correct