답안 #31291 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31291	2017-08-17T22:21:00 Z	imaxblue	Pipes (BOI13_pipes)	C++14	36.1481 / 100	636 ms	23792 KB

pipes

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	9932 KB	Output is correct
2	Correct	0 ms	9932 KB	Output is correct
3	Correct	0 ms	9932 KB	Output is correct
4	Runtime error	189 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	0 ms	9932 KB	Output is correct
9	Correct	3 ms	9932 KB	Output is correct
10	Correct	3 ms	9932 KB	Output is correct
11	Correct	6 ms	9932 KB	Output is correct
12	Correct	3 ms	9932 KB	Output is correct
13	Correct	179 ms	13100 KB	Output is correct
14	Runtime error	206 ms	13628 KB	Execution timed out (wall clock limit exceeded)
15	Correct	236 ms	13892 KB	Output is correct
16	Runtime error	239 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	209 ms	13892 KB	Execution timed out (wall clock limit exceeded)
19	Runtime error	229 ms	13100 KB	Execution timed out (wall clock limit exceeded)
20	Correct	0 ms	9932 KB	Output is correct
21	Correct	0 ms	9932 KB	Output is correct
22	Runtime error	253 ms	13892 KB	Execution timed out (wall clock limit exceeded)
23	Runtime error	153 ms	13100 KB	Execution timed out (wall clock limit exceeded)
24	Runtime error	193 ms	13892 KB	Execution timed out (wall clock limit exceeded)
25	Runtime error	199 ms	13236 KB	Execution timed out (wall clock limit exceeded)

Subtask #2
18.1481481481 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	9932 KB	Output isn't correct
2	Incorrect	0 ms	9932 KB	Output isn't correct
3	Correct	156 ms	17964 KB	Output is correct
4	Runtime error	286 ms	21280 KB	Execution timed out (wall clock limit exceeded)
5	Incorrect	206 ms	13688 KB	Output isn't correct
6	Correct	576 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	0 ms	9932 KB	Output isn't correct
12	Incorrect	0 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	0 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	0 ms	9932 KB	Output isn't correct
21	Correct	3 ms	10064 KB	Output is correct
22	Incorrect	0 ms	9932 KB	Output isn't correct
23	Incorrect	239 ms	18052 KB	Output isn't correct
24	Runtime error	269 ms	18804 KB	Execution timed out (wall clock limit exceeded)
25	Correct	149 ms	17964 KB	Output is correct
26	Incorrect	246 ms	19228 KB	Output isn't correct
27	Runtime error	209 ms	20960 KB	Execution timed out (wall clock limit exceeded)
28	Runtime error	236 ms	13764 KB	Execution timed out (wall clock limit exceeded)
29	Correct	429 ms	21152 KB	Output is correct
30	Runtime error	226 ms	17736 KB	Execution timed out (wall clock limit exceeded)
31	Runtime error	226 ms	22292 KB	Execution timed out (wall clock limit exceeded)
32	Runtime error	176 ms	15560 KB	Execution timed out (wall clock limit exceeded)
33	Correct	123 ms	19004 KB	Output is correct
34	Incorrect	226 ms	19052 KB	Output isn't correct
35	Runtime error	199 ms	21276 KB	Execution timed out (wall clock limit exceeded)
36	Runtime error	209 ms	13628 KB	Execution timed out (wall clock limit exceeded)
37	Correct	636 ms	23792 KB	Output is correct
38	Runtime error	223 ms	18028 KB	Execution timed out (wall clock limit exceeded)
39	Runtime error	186 ms	14756 KB	Execution timed out (wall clock limit exceeded)
40	Incorrect	273 ms	18372 KB	Output isn't correct
41	Correct	193 ms	22296 KB	Output is correct
42	Runtime error	229 ms	19456 KB	Execution timed out (wall clock limit exceeded)
43	Incorrect	259 ms	21768 KB	Output isn't correct
44	Runtime error	219 ms	13688 KB	Execution timed out (wall clock limit exceeded)
45	Correct	453 ms	22208 KB	Output is correct
46	Incorrect	263 ms	17356 KB	Output isn't correct
47	Incorrect	233 ms	18508 KB	Output isn't correct
48	Incorrect	269 ms	22032 KB	Output isn't correct
49	Correct	163 ms	14932 KB	Output is correct
50	Runtime error	259 ms	19116 KB	Execution timed out (wall clock limit exceeded)
51	Runtime error	239 ms	17808 KB	Execution timed out (wall clock limit exceeded)
52	Runtime error	206 ms	15764 KB	Execution timed out (wall clock limit exceeded)
53	Correct	579 ms	21944 KB	Output is correct
54	Incorrect	286 ms	17156 KB	Output isn't correct

답안 #31291

Compilation message

Subtask #1 18.0 / 30.0

Subtask #2 18.1481481481 / 70.0

Subtask #1
18.0 / 30.0

Subtask #2
18.1481481481 / 70.0