oj.uz

Submission #31292

# Submission time Handle Problem Language Result Execution time Memory
31292 2017-08-17T22:58:18 Z imaxblue Pipes (BOI13_pipes) C++14
18 / 100
 806 ms 23792 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;
ll c[100005], f[500005], k;
int in[100005], u[100005];
bool u2[100005];
vector<pii> v[100005], s;
queue<int> q;
void dfs(int N, int P, int C){
    //cout << N << ' ' << C << endl;
    if (u[N]){
        //cout << "*" << endl;
        if (u[N]==C){
            cout << 0 << endl;
            exit(0);
        }
        /*if (u2[N]) return;
        s.pb(mp(N, -1));
        fox(l, s.size()-1){
            u2[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;
        //s.pb(mp(N, v[N][l].y));
        dfs(v[N][l].x, N, 3-C);
        //s.pop_back();
    }
}
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]==0) 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;
        //dfs(l, -1, 1);
    }
    fox(l, m){
        cout << f[l]*2 << endl;
    }
    return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int, 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: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:81:9: note: in expansion of macro 'fox'
         fox(l, v[N].size()){
         ^

Subtask #1
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9932 KB Output is correct
2 Correct 3 ms 9932 KB Output is correct
3 Correct 0 ms 9932 KB Output is correct
4 Runtime error 209 ms 13892 KB Execution timed out (wall clock limit exceeded)
5 Correct 0 ms 9932 KB Output is correct
6 Correct 0 ms 9932 KB Output is correct
7 Correct 0 ms 9932 KB Output is correct
8 Correct 3 ms 9932 KB Output is correct
9 Correct 3 ms 9932 KB Output is correct
10 Correct 0 ms 9932 KB Output is correct
11 Correct 6 ms 9932 KB Output is correct
12 Correct 6 ms 9932 KB Output is correct
13 Correct 213 ms 13100 KB Output is correct
14 Runtime error 216 ms 13628 KB Execution timed out (wall clock limit exceeded)
15 Runtime error 183 ms 13892 KB Execution timed out (wall clock limit exceeded)
16 Runtime error 199 ms 13232 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 263 ms 13892 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 246 ms 13892 KB Execution timed out (wall clock limit exceeded)
19 Runtime error 253 ms 13100 KB Execution timed out (wall clock limit exceeded)
20 Correct 0 ms 9932 KB Output is correct
21 Correct 6 ms 9932 KB Output is correct
22 Runtime error 189 ms 13892 KB Execution timed out (wall clock limit exceeded)
23 Correct 189 ms 13100 KB Output is correct
24 Runtime error 189 ms 13892 KB Execution timed out (wall clock limit exceeded)
25 Runtime error 183 ms 13236 KB Execution timed out (wall clock limit exceeded)

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9932 KB Output isn't correct
2 Incorrect 0 ms 9932 KB Output isn't correct
3 Runtime error 266 ms 13364 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 263 ms 13232 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 179 ms 13628 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 603 ms 23792 KB Execution timed out (wall clock limit exceeded)
7 Incorrect 0 ms 9932 KB Output isn't correct
8 Incorrect 3 ms 9932 KB Output isn't correct
9 Incorrect 0 ms 9932 KB Output isn't correct
10 Incorrect 0 ms 9932 KB Output isn't correct
11 Incorrect 0 ms 9932 KB Output isn't correct
12 Incorrect 3 ms 9932 KB Output isn't correct
13 Incorrect 0 ms 9932 KB Output isn't correct
14 Incorrect 3 ms 9932 KB Output isn't correct
15 Incorrect 13 ms 9932 KB Output isn't correct
16 Incorrect 6 ms 9932 KB Output isn't correct
17 Incorrect 0 ms 9932 KB Output isn't correct
18 Incorrect 0 ms 9932 KB Output isn't correct
19 Incorrect 0 ms 9932 KB Output isn't correct
20 Incorrect 0 ms 9932 KB Output isn't correct
21 Incorrect 6 ms 10064 KB Output isn't correct
22 Incorrect 0 ms 9932 KB Output isn't correct
23 Runtime error 179 ms 12704 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 199 ms 13496 KB Execution timed out (wall clock limit exceeded)
25 Runtime error 199 ms 13364 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 223 ms 13364 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 233 ms 13100 KB Execution timed out (wall clock limit exceeded)
28 Incorrect 313 ms 13764 KB Output isn't correct
29 Runtime error 493 ms 21152 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 226 ms 13100 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 243 ms 13232 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 229 ms 13760 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 209 ms 13496 KB Execution timed out (wall clock limit exceeded)
34 Runtime error 193 ms 13232 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 226 ms 13232 KB Execution timed out (wall clock limit exceeded)
36 Incorrect 266 ms 13628 KB Output isn't correct
37 Runtime error 806 ms 23792 KB Execution timed out (wall clock limit exceeded)
38 Incorrect 239 ms 13232 KB Output isn't correct
39 Incorrect 249 ms 13760 KB Output isn't correct
40 Incorrect 256 ms 13496 KB Output isn't correct
41 Incorrect 226 ms 13232 KB Output isn't correct
42 Incorrect 256 ms 13100 KB Output isn't correct
43 Incorrect 236 ms 13100 KB Output isn't correct
44 Incorrect 239 ms 13628 KB Output isn't correct
45 Runtime error 596 ms 22208 KB Execution timed out (wall clock limit exceeded)
46 Runtime error 183 ms 13100 KB Execution timed out (wall clock limit exceeded)
47 Runtime error 189 ms 13496 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 206 ms 13232 KB Execution timed out (wall clock limit exceeded)
49 Incorrect 239 ms 13628 KB Output isn't correct
50 Runtime error 196 ms 13364 KB Execution timed out (wall clock limit exceeded)
51 Incorrect 249 ms 13496 KB Output isn't correct
52 Incorrect 283 ms 13232 KB Output isn't correct
53 Runtime error 626 ms 21944 KB Execution timed out (wall clock limit exceeded)
54 Runtime error 189 ms 13232 KB Execution timed out (wall clock limit exceeded)