oj.uz

Submission #31313

# Submission time Handle Problem Language Result Execution time Memory
31313 2017-08-18T00:00:37 Z imaxblue Pipes (BOI13_pipes) C++14
54.2 / 100
 633 ms 21060 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;
int 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()){
     ^
pipes.cpp: In function 'int main()':
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:83:9: note: in expansion of macro 'fox'
         fox(l, v[N].size()){
         ^

Subtask #1
19.2 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7200 KB Output is correct
2 Correct 0 ms 7200 KB Output is correct
3 Correct 0 ms 7200 KB Output is correct
4 Correct 253 ms 11160 KB Output is correct
5 Correct 0 ms 7200 KB Output is correct
6 Correct 0 ms 7200 KB Output is correct
7 Correct 0 ms 7200 KB Output is correct
8 Correct 0 ms 7200 KB Output is correct
9 Correct 0 ms 7200 KB Output is correct
10 Correct 0 ms 7200 KB Output is correct
11 Correct 3 ms 7200 KB Output is correct
12 Correct 0 ms 7200 KB Output is correct
13 Correct 199 ms 10368 KB Output is correct
14 Runtime error 246 ms 10896 KB Execution timed out (wall clock limit exceeded)
15 Runtime error 263 ms 11160 KB Execution timed out (wall clock limit exceeded)
16 Runtime error 209 ms 10500 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 193 ms 11160 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 219 ms 11160 KB Execution timed out (wall clock limit exceeded)
19 Runtime error 193 ms 10368 KB Execution timed out (wall clock limit exceeded)
20 Correct 0 ms 7200 KB Output is correct
21 Correct 9 ms 7200 KB Output is correct
22 Runtime error 209 ms 11160 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 146 ms 10368 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 169 ms 11160 KB Execution timed out (wall clock limit exceeded)
25 Correct 216 ms 10504 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 7200 KB Output isn't correct
2 Incorrect 3 ms 7200 KB Output isn't correct
3 Correct 119 ms 15232 KB Output is correct
4 Runtime error 243 ms 18552 KB Execution timed out (wall clock limit exceeded)
5 Correct 156 ms 10896 KB Output is correct
6 Correct 516 ms 21060 KB Output is correct
7 Incorrect 0 ms 7200 KB Output isn't correct
8 Incorrect 3 ms 7200 KB Output isn't correct
9 Correct 0 ms 7200 KB Output is correct
10 Incorrect 0 ms 7200 KB Output isn't correct
11 Incorrect 0 ms 7200 KB Output isn't correct
12 Correct 0 ms 7200 KB Output is correct
13 Correct 0 ms 7200 KB Output is correct
14 Incorrect 3 ms 7200 KB Output isn't correct
15 Incorrect 0 ms 7200 KB Output isn't correct
16 Incorrect 0 ms 7200 KB Output isn't correct
17 Correct 0 ms 7200 KB Output is correct
18 Incorrect 0 ms 7200 KB Output isn't correct
19 Incorrect 6 ms 7200 KB Output isn't correct
20 Correct 3 ms 7200 KB Output is correct
21 Correct 0 ms 7332 KB Output is correct
22 Incorrect 0 ms 7200 KB Output isn't correct
23 Runtime error 203 ms 15324 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 243 ms 16072 KB Execution timed out (wall clock limit exceeded)
25 Correct 163 ms 15236 KB Output is correct
26 Correct 186 ms 16500 KB Output is correct
27 Correct 143 ms 13544 KB Output is correct
28 Correct 189 ms 11032 KB Output is correct
29 Correct 563 ms 18420 KB Output is correct
30 Runtime error 263 ms 15008 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 233 ms 19560 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 199 ms 12828 KB Execution timed out (wall clock limit exceeded)
33 Correct 169 ms 16276 KB Output is correct
34 Correct 166 ms 16324 KB Output is correct
35 Runtime error 259 ms 18544 KB Execution timed out (wall clock limit exceeded)
36 Correct 159 ms 10896 KB Output is correct
37 Correct 633 ms 21060 KB Output is correct
38 Runtime error 229 ms 15300 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 196 ms 12024 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 213 ms 15644 KB Execution timed out (wall clock limit exceeded)
41 Correct 153 ms 19564 KB Output is correct
42 Correct 173 ms 16728 KB Output is correct
43 Correct 163 ms 19036 KB Output is correct
44 Correct 173 ms 10896 KB Output is correct
45 Correct 469 ms 19476 KB Output is correct
46 Incorrect 236 ms 14624 KB Output isn't correct
47 Runtime error 206 ms 15780 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 266 ms 19304 KB Execution timed out (wall clock limit exceeded)
49 Correct 153 ms 12204 KB Output is correct
50 Runtime error 233 ms 16384 KB Execution timed out (wall clock limit exceeded)
51 Correct 219 ms 15076 KB Output is correct
52 Correct 179 ms 11924 KB Output is correct
53 Correct 516 ms 19212 KB Output is correct
54 Runtime error 239 ms 14432 KB Execution timed out (wall clock limit exceeded)