답안 #31293 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31293	2017-08-17T22:59:54 Z	imaxblue	Pipes (BOI13_pipes)	C++14	18.1481 / 100	679 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: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
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	9932 KB	Output isn't correct
2	Incorrect	0 ms	9932 KB	Output isn't correct
3	Incorrect	0 ms	9932 KB	Output isn't correct
4	Incorrect	159 ms	13892 KB	Output isn't correct
5	Incorrect	0 ms	9932 KB	Output isn't correct
6	Incorrect	0 ms	9932 KB	Output isn't correct
7	Incorrect	0 ms	9932 KB	Output isn't correct
8	Incorrect	0 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	0 ms	9932 KB	Output isn't correct
13	Incorrect	146 ms	13100 KB	Output isn't correct
14	Incorrect	163 ms	13628 KB	Output isn't correct
15	Incorrect	179 ms	13892 KB	Output isn't correct
16	Incorrect	126 ms	13232 KB	Output isn't correct
17	Incorrect	169 ms	13892 KB	Output isn't correct
18	Incorrect	143 ms	13892 KB	Output isn't correct
19	Incorrect	163 ms	13100 KB	Output isn't correct
20	Incorrect	0 ms	9932 KB	Output isn't correct
21	Incorrect	3 ms	9932 KB	Output isn't correct
22	Incorrect	169 ms	13892 KB	Output isn't correct
23	Incorrect	133 ms	13100 KB	Output isn't correct
24	Incorrect	189 ms	13892 KB	Output isn't correct
25	Incorrect	129 ms	13236 KB	Output isn't correct

Subtask #2
18.1481481481 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	9932 KB	Output isn't correct
2	Incorrect	3 ms	9932 KB	Output isn't correct
3	Correct	186 ms	17960 KB	Output is correct
4	Incorrect	216 ms	21276 KB	Output isn't correct
5	Incorrect	219 ms	13688 KB	Output isn't correct
6	Correct	679 ms	23792 KB	Output is correct
7	Incorrect	0 ms	9932 KB	Output isn't correct
8	Incorrect	0 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	0 ms	9932 KB	Output is correct
18	Incorrect	3 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	0 ms	10064 KB	Output is correct
22	Incorrect	0 ms	9932 KB	Output isn't correct
23	Incorrect	146 ms	18048 KB	Output isn't correct
24	Incorrect	223 ms	18804 KB	Output isn't correct
25	Correct	126 ms	17968 KB	Output is correct
26	Incorrect	156 ms	19228 KB	Output isn't correct
27	Incorrect	139 ms	20960 KB	Output isn't correct
28	Incorrect	216 ms	13764 KB	Output isn't correct
29	Correct	493 ms	21152 KB	Output is correct
30	Incorrect	153 ms	17736 KB	Output isn't correct
31	Incorrect	173 ms	22292 KB	Output isn't correct
32	Incorrect	159 ms	15564 KB	Output isn't correct
33	Correct	149 ms	19008 KB	Output is correct
34	Incorrect	159 ms	19056 KB	Output isn't correct
35	Incorrect	179 ms	21276 KB	Output isn't correct
36	Incorrect	183 ms	13628 KB	Output isn't correct
37	Correct	633 ms	23792 KB	Output is correct
38	Incorrect	153 ms	18032 KB	Output isn't correct
39	Incorrect	156 ms	14760 KB	Output isn't correct
40	Incorrect	149 ms	18372 KB	Output isn't correct
41	Correct	156 ms	22296 KB	Output is correct
42	Incorrect	176 ms	19456 KB	Output isn't correct
43	Incorrect	169 ms	21768 KB	Output isn't correct
44	Incorrect	159 ms	13692 KB	Output isn't correct
45	Correct	456 ms	22208 KB	Output is correct
46	Incorrect	149 ms	17352 KB	Output isn't correct
47	Incorrect	139 ms	18508 KB	Output isn't correct
48	Incorrect	176 ms	22032 KB	Output isn't correct
49	Correct	146 ms	14932 KB	Output is correct
50	Incorrect	173 ms	19112 KB	Output isn't correct
51	Incorrect	186 ms	17804 KB	Output isn't correct
52	Incorrect	173 ms	15764 KB	Output isn't correct
53	Correct	499 ms	21944 KB	Output is correct
54	Incorrect	186 ms	17160 KB	Output isn't correct

답안 #31293

Compilation message

Subtask #1 0 / 30.0

Subtask #2 18.1481481481 / 70.0

Subtask #1
0 / 30.0

Subtask #2
18.1481481481 / 70.0