Submission #153711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
153711	2019-09-15T10:08:15 Z	brcode	Pipes (BOI13_pipes)	C++14	35.1852 / 100	1000 ms	131076 KB

pipes

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const long long MAXN = 1e5+5;
long long p[MAXN];
long long dep[MAXN];
long long val[MAXN];
long long node[MAXN];
vector<long long> v1[MAXN];
vector<long long> v2[MAXN];
long long maxdepth;
map<pair<long long,long long>,long long> m1;
vector<long long> process;
long long ans[MAXN];
void dfs(long long curr,long long par,long long depth){
    p[curr] = par;
    dep[curr] = depth;
    v2[depth].push_back(curr);
    maxdepth = max(maxdepth,depth);
    for(long long x:v1[curr]){
        if(x!=par){
            dfs(x,curr,depth+1);
        }
    }
    
}
int main(){
    long long n,m;
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>val[i];
    }
    for(long long i=1;i<n;i++){
        long long x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
        m1[make_pair(x,y)] = i;
        
        m1[make_pair(y,x)] = i;
    }
    dfs(1,0,1);
    for(long long i=maxdepth;i>=1;i--){
        for(long long x:v2[i]){
            process.push_back(x);
        }
    }
    for(long long x:process){
        long long edgew = (val[x]-node[x])*2;
        node[p[x]]+=val[x]-node[x];
        ans[m1[make_pair(x,p[x])]] = edgew;
    }
    if(node[0]!=0){
        cout<<0<<endl;
        return 0;
    }
    for(long long i=1;i<n;i++){
        cout<<ans[i]<<endl;
    }
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	6 ms	4988 KB	Output is correct
3	Correct	11 ms	5240 KB	Output is correct
4	Correct	713 ms	29140 KB	Output is correct
5	Correct	7 ms	4984 KB	Output is correct
6	Correct	7 ms	5064 KB	Output is correct
7	Correct	7 ms	5112 KB	Output is correct
8	Correct	7 ms	5112 KB	Output is correct
9	Correct	11 ms	5212 KB	Output is correct
10	Correct	12 ms	5240 KB	Output is correct
11	Correct	11 ms	5368 KB	Output is correct
12	Correct	11 ms	5240 KB	Output is correct
13	Correct	546 ms	24300 KB	Output is correct
14	Correct	645 ms	27824 KB	Output is correct
15	Correct	689 ms	29324 KB	Output is correct
16	Correct	584 ms	25736 KB	Output is correct
17	Correct	705 ms	29008 KB	Output is correct
18	Correct	691 ms	29304 KB	Output is correct
19	Correct	692 ms	32316 KB	Output is correct
20	Correct	7 ms	4984 KB	Output is correct
21	Correct	11 ms	5240 KB	Output is correct
22	Correct	737 ms	29336 KB	Output is correct
23	Correct	536 ms	24224 KB	Output is correct
24	Correct	698 ms	29356 KB	Output is correct
25	Correct	581 ms	25176 KB	Output is correct

Subtask #2

5.18518518519 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	43 ms	29816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Incorrect	9 ms	5368 KB	Output isn't correct
3	Incorrect	672 ms	30088 KB	Output isn't correct
4	Runtime error	387 ms	68208 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	345 ms	69388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	338 ms	67460 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	43 ms	29944 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	59 ms	35448 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Incorrect	8 ms	5112 KB	Output isn't correct
10	Runtime error	41 ms	29176 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	41 ms	29180 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	61 ms	34296 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	88 ms	29252 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	94 ms	29740 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Incorrect	10 ms	5368 KB	Output isn't correct
16	Runtime error	54 ms	30584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Incorrect	13 ms	5368 KB	Output isn't correct
18	Runtime error	71 ms	34296 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Correct	8 ms	5240 KB	Output is correct
20	Correct	8 ms	5240 KB	Output is correct
21	Runtime error	87 ms	29560 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Incorrect	8 ms	5368 KB	Output isn't correct
23	Runtime error	409 ms	95920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Incorrect	464 ms	31596 KB	Output isn't correct
25	Incorrect	733 ms	30136 KB	Output isn't correct
26	Correct	423 ms	28332 KB	Output is correct
27	Runtime error	359 ms	67064 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	335 ms	65620 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	393 ms	66880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Incorrect	458 ms	34360 KB	Output isn't correct
31	Incorrect	455 ms	34024 KB	Output isn't correct
32	Runtime error	415 ms	73348 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	459 ms	111012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	352 ms	67832 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	441 ms	68184 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	1002 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
37	Runtime error	337 ms	67532 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Incorrect	521 ms	31228 KB	Output isn't correct
39	Runtime error	443 ms	76408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Incorrect	442 ms	31084 KB	Output isn't correct
41	Incorrect	704 ms	35252 KB	Output isn't correct
42	Correct	333 ms	28264 KB	Output is correct
43	Runtime error	427 ms	105860 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	336 ms	69520 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	184 ms	49392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Incorrect	428 ms	33260 KB	Output isn't correct
47	Runtime error	458 ms	112984 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Incorrect	425 ms	34924 KB	Output isn't correct
49	Runtime error	417 ms	70912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	439 ms	108436 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	466 ms	111788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	334 ms	66856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	280 ms	55360 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Incorrect	486 ms	32488 KB	Output isn't correct