oj.uz

Submission #31288

# Submission time Handle Problem Language Result Execution time Memory
31288 2017-08-17T22:07:27 Z imaxblue Pipes (BOI13_pipes) C++14
38.5481 / 100
 659 ms 21448 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, k;
int c[100005], f[500005], 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 (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:41: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:48: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:56: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:79:9: note: in expansion of macro 'fox'
         fox(l, v[N].size()){
         ^

Subtask #1
20.4 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7588 KB Output is correct
2 Correct 0 ms 7588 KB Output is correct
3 Correct 6 ms 7588 KB Output is correct
4 Runtime error 219 ms 11548 KB Execution timed out (wall clock limit exceeded)
5 Correct 0 ms 7588 KB Output is correct
6 Correct 0 ms 7588 KB Output is correct
7 Correct 3 ms 7588 KB Output is correct
8 Correct 0 ms 7588 KB Output is correct
9 Correct 6 ms 7588 KB Output is correct
10 Correct 3 ms 7588 KB Output is correct
11 Correct 3 ms 7588 KB Output is correct
12 Correct 9 ms 7588 KB Output is correct
13 Runtime error 219 ms 10756 KB Execution timed out (wall clock limit exceeded)
14 Correct 216 ms 11284 KB Output is correct
15 Runtime error 229 ms 11548 KB Execution timed out (wall clock limit exceeded)
16 Correct 216 ms 10888 KB Output is correct
17 Runtime error 243 ms 11548 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 206 ms 11548 KB Execution timed out (wall clock limit exceeded)
19 Correct 333 ms 10756 KB Output is correct
20 Correct 0 ms 7588 KB Output is correct
21 Correct 3 ms 7588 KB Output is correct
22 Runtime error 259 ms 11548 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 143 ms 10756 KB Execution timed out (wall clock limit exceeded)
24 Correct 249 ms 11548 KB Output is correct
25 Runtime error 169 ms 10892 KB Execution timed out (wall clock limit exceeded)

Subtask #2
18.1481481481 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7588 KB Output isn't correct
2 Incorrect 0 ms 7588 KB Output isn't correct
3 Correct 193 ms 14928 KB Output is correct
4 Runtime error 276 ms 17756 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 226 ms 11316 KB Execution timed out (wall clock limit exceeded)
6 Correct 623 ms 21448 KB Output is correct
7 Incorrect 0 ms 7588 KB Output isn't correct
8 Incorrect 0 ms 7588 KB Output isn't correct
9 Correct 0 ms 7588 KB Output is correct
10 Incorrect 3 ms 7588 KB Output isn't correct
11 Incorrect 3 ms 7588 KB Output isn't correct
12 Incorrect 0 ms 7588 KB Output isn't correct
13 Correct 0 ms 7588 KB Output is correct
14 Incorrect 3 ms 7588 KB Output isn't correct
15 Incorrect 6 ms 7588 KB Output isn't correct
16 Incorrect 3 ms 7588 KB Output isn't correct
17 Correct 3 ms 7588 KB Output is correct
18 Incorrect 3 ms 7588 KB Output isn't correct
19 Incorrect 6 ms 7588 KB Output isn't correct
20 Incorrect 6 ms 7588 KB Output isn't correct
21 Correct 3 ms 7720 KB Output is correct
22 Incorrect 3 ms 7588 KB Output isn't correct
23 Runtime error 203 ms 14892 KB Execution timed out (wall clock limit exceeded)
24 Incorrect 306 ms 15636 KB Output isn't correct
25 Correct 149 ms 14932 KB Output is correct
26 Runtime error 239 ms 15972 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 246 ms 17468 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 283 ms 11420 KB Execution timed out (wall clock limit exceeded)
29 Correct 513 ms 18808 KB Output is correct
30 Incorrect 226 ms 15544 KB Output isn't correct
31 Runtime error 253 ms 18584 KB Execution timed out (wall clock limit exceeded)
32 Incorrect 293 ms 12960 KB Output isn't correct
33 Correct 166 ms 15804 KB Output is correct
34 Runtime error 266 ms 15820 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 303 ms 17760 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 186 ms 11284 KB Execution timed out (wall clock limit exceeded)
37 Correct 659 ms 21448 KB Output is correct
38 Incorrect 256 ms 17608 KB Output isn't correct
39 Runtime error 223 ms 12248 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 243 ms 15276 KB Execution timed out (wall clock limit exceeded)
41 Correct 163 ms 18588 KB Output is correct
42 Runtime error 266 ms 16132 KB Execution timed out (wall clock limit exceeded)
43 Runtime error 209 ms 18140 KB Execution timed out (wall clock limit exceeded)
44 Runtime error 189 ms 11320 KB Execution timed out (wall clock limit exceeded)
45 Correct 446 ms 19864 KB Output is correct
46 Runtime error 253 ms 19168 KB Execution timed out (wall clock limit exceeded)
47 Runtime error 203 ms 15388 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 283 ms 18380 KB Execution timed out (wall clock limit exceeded)
49 Correct 149 ms 12368 KB Output is correct
50 Runtime error 263 ms 15884 KB Execution timed out (wall clock limit exceeded)
51 Runtime error 243 ms 14800 KB Execution timed out (wall clock limit exceeded)
52 Runtime error 233 ms 13028 KB Execution timed out (wall clock limit exceeded)
53 Correct 453 ms 19600 KB Output is correct
54 Runtime error 233 ms 15592 KB Execution timed out (wall clock limit exceeded)