oj.uz

Submission #31290

# Submission time Handle Problem Language Result Execution time Memory
31290 2017-08-17T22:19:03 Z imaxblue Pipes (BOI13_pipes) C++14
39.7481 / 100
 616 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: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:81:9: note: in expansion of macro 'fox'
         fox(l, v[N].size()){
         ^

Subtask #1
21.6 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9932 KB Output is correct
2 Correct 0 ms 9932 KB Output is correct
3 Correct 3 ms 9932 KB Output is correct
4 Runtime error 199 ms 13892 KB Execution timed out (wall clock limit exceeded)
5 Correct 0 ms 9932 KB Output is correct
6 Correct 3 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 6 ms 9932 KB Output is correct
10 Correct 6 ms 9932 KB Output is correct
11 Correct 3 ms 9932 KB Output is correct
12 Correct 0 ms 9932 KB Output is correct
13 Correct 189 ms 13100 KB Output is correct
14 Runtime error 213 ms 13628 KB Execution timed out (wall clock limit exceeded)
15 Runtime error 216 ms 13892 KB Execution timed out (wall clock limit exceeded)
16 Runtime error 203 ms 13232 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 206 ms 13892 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 263 ms 13892 KB Execution timed out (wall clock limit exceeded)
19 Correct 209 ms 13100 KB Output is correct
20 Correct 0 ms 9932 KB Output is correct
21 Correct 3 ms 9932 KB Output is correct
22 Runtime error 189 ms 13892 KB Execution timed out (wall clock limit exceeded)
23 Correct 196 ms 13100 KB Output is correct
24 Correct 233 ms 13892 KB Output is correct
25 Correct 203 ms 13236 KB Output is correct

Subtask #2
18.1481481481 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9932 KB Output isn't correct
2 Incorrect 9 ms 9932 KB Output isn't correct
3 Correct 149 ms 17964 KB Output is correct
4 Runtime error 216 ms 21280 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 216 ms 13688 KB Execution timed out (wall clock limit exceeded)
6 Correct 616 ms 23792 KB Output is correct
7 Incorrect 0 ms 9932 KB Output isn't correct
8 Incorrect 3 ms 9932 KB Output isn't correct
9 Correct 0 ms 9932 KB Output is correct
10 Incorrect 0 ms 9932 KB Output isn't correct
11 Incorrect 3 ms 9932 KB Output isn't correct
12 Incorrect 3 ms 9932 KB Output isn't correct
13 Correct 0 ms 9932 KB Output is correct
14 Incorrect 0 ms 9932 KB Output isn't correct
15 Incorrect 3 ms 9932 KB Output isn't correct
16 Incorrect 0 ms 9932 KB Output isn't correct
17 Correct 3 ms 9932 KB Output is correct
18 Incorrect 6 ms 9932 KB Output isn't correct
19 Incorrect 0 ms 9932 KB Output isn't correct
20 Incorrect 3 ms 9932 KB Output isn't correct
21 Correct 0 ms 10064 KB Output is correct
22 Incorrect 6 ms 9932 KB Output isn't correct
23 Runtime error 196 ms 18056 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 209 ms 18804 KB Execution timed out (wall clock limit exceeded)
25 Correct 176 ms 17964 KB Output is correct
26 Runtime error 286 ms 19228 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 173 ms 20952 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 246 ms 13764 KB Execution timed out (wall clock limit exceeded)
29 Correct 516 ms 21152 KB Output is correct
30 Incorrect 273 ms 17736 KB Output isn't correct
31 Incorrect 243 ms 22292 KB Output isn't correct
32 Runtime error 219 ms 15556 KB Execution timed out (wall clock limit exceeded)
33 Correct 126 ms 19008 KB Output is correct
34 Runtime error 279 ms 19060 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 253 ms 21280 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 306 ms 13628 KB Execution timed out (wall clock limit exceeded)
37 Correct 593 ms 23792 KB Output is correct
38 Runtime error 209 ms 18028 KB Execution timed out (wall clock limit exceeded)
39 Incorrect 256 ms 14760 KB Output isn't correct
40 Runtime error 266 ms 18372 KB Execution timed out (wall clock limit exceeded)
41 Correct 189 ms 22292 KB Output is correct
42 Runtime error 219 ms 19460 KB Execution timed out (wall clock limit exceeded)
43 Runtime error 223 ms 21764 KB Execution timed out (wall clock limit exceeded)
44 Runtime error 226 ms 13688 KB Execution timed out (wall clock limit exceeded)
45 Correct 523 ms 22208 KB Output is correct
46 Runtime error 269 ms 17352 KB Execution timed out (wall clock limit exceeded)
47 Runtime error 209 ms 18512 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 213 ms 22036 KB Execution timed out (wall clock limit exceeded)
49 Correct 123 ms 14936 KB Output is correct
50 Runtime error 213 ms 19116 KB Execution timed out (wall clock limit exceeded)
51 Incorrect 263 ms 17804 KB Output isn't correct
52 Runtime error 193 ms 15760 KB Execution timed out (wall clock limit exceeded)
53 Correct 513 ms 21944 KB Output is correct
54 Runtime error 269 ms 17156 KB Execution timed out (wall clock limit exceeded)