답안 #153617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153617	2019-09-15T04:23:51 Z	brcode	Pipes (BOI13_pipes)	C++14	10.3704 / 100	1000 ms	131076 KB

pipes

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const long long MAXN = 5e5+5;
vector<long long> v1[MAXN];
long long p[MAXN];
vector<long long> leaves;
long long val[MAXN];
map<pair<long long,long long>,long long> m1;
long long node[MAXN];
long long ans[MAXN];
void dfs(long long curr,long long par){

    p[curr] = par;
    for(long long x:v1[curr]){
        if(x!=par){
            dfs(x,curr);
        }
    }

    if(v1[curr].size() == 1 && curr!=1){
        leaves.push_back(curr);

    }
}
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);
    queue<long long> q1;
    for(long long x:leaves){
        q1.push(x);
    }

    while(!q1.empty()){
        long long curr =q1.front();
        q1.pop();
        if(curr == 0){
            break;
        }
        long long edgew = (val[curr]-node[curr])*2;
        node[p[curr]]+=val[curr]-node[curr];
        ans[m1[make_pair(p[curr],curr)]] = edgew;
        q1.push(p[curr]);
    }
    if(node[0]){
        cout<<0<<endl;
        return 0;
    }
    for(long long i=1;i<n;i++){
        cout<<ans[i]<<endl;
    }


}

Subtask #1

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	12280 KB	Output isn't correct
2	Incorrect	13 ms	12152 KB	Output isn't correct
3	Incorrect	16 ms	12280 KB	Output isn't correct
4	Incorrect	452 ms	34032 KB	Output isn't correct
5	Incorrect	13 ms	12152 KB	Output isn't correct
6	Incorrect	13 ms	12168 KB	Output isn't correct
7	Incorrect	13 ms	12168 KB	Output isn't correct
8	Incorrect	13 ms	12156 KB	Output isn't correct
9	Incorrect	15 ms	12280 KB	Output isn't correct
10	Incorrect	15 ms	12280 KB	Output isn't correct
11	Incorrect	16 ms	12280 KB	Output isn't correct
12	Incorrect	15 ms	12280 KB	Output isn't correct
13	Incorrect	341 ms	29556 KB	Output isn't correct
14	Incorrect	414 ms	32764 KB	Output isn't correct
15	Incorrect	513 ms	34008 KB	Output isn't correct
16	Incorrect	364 ms	30804 KB	Output isn't correct
17	Incorrect	430 ms	33776 KB	Output isn't correct
18	Incorrect	429 ms	33952 KB	Output isn't correct
19	Incorrect	683 ms	34936 KB	Output isn't correct
20	Incorrect	13 ms	12152 KB	Output isn't correct
21	Incorrect	15 ms	12280 KB	Output isn't correct
22	Incorrect	536 ms	34120 KB	Output isn't correct
23	Incorrect	413 ms	29424 KB	Output isn't correct
24	Incorrect	430 ms	34044 KB	Output isn't correct
25	Incorrect	347 ms	30296 KB	Output isn't correct

Subtask #2

10.3703703704 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	141 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Incorrect	15 ms	12284 KB	Output isn't correct
3	Correct	368 ms	33592 KB	Output is correct
4	Execution timed out	1046 ms	131076 KB	Time limit exceeded
5	Runtime error	465 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	418 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	134 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	189 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Correct	13 ms	12152 KB	Output is correct
10	Runtime error	125 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	125 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	208 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	130 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	222 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Incorrect	16 ms	12280 KB	Output isn't correct
16	Runtime error	197 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Correct	17 ms	12280 KB	Output is correct
18	Runtime error	282 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Correct	15 ms	12280 KB	Output is correct
20	Correct	15 ms	12280 KB	Output is correct
21	Runtime error	131 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Incorrect	16 ms	12280 KB	Output isn't correct
23	Runtime error	744 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
24	Execution timed out	1060 ms	35088 KB	Time limit exceeded
25	Correct	375 ms	33652 KB	Output is correct
26	Correct	449 ms	33324 KB	Output is correct
27	Runtime error	818 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
28	Runtime error	393 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
29	Runtime error	437 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Execution timed out	1077 ms	35960 KB	Time limit exceeded
31	Execution timed out	1080 ms	36268 KB	Time limit exceeded
32	Execution timed out	1043 ms	111732 KB	Time limit exceeded
33	Runtime error	830 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
34	Runtime error	544 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
35	Execution timed out	1078 ms	119928 KB	Time limit exceeded
36	Execution timed out	1086 ms	99036 KB	Time limit exceeded
37	Runtime error	417 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
38	Execution timed out	1079 ms	34572 KB	Time limit exceeded
39	Execution timed out	1091 ms	112540 KB	Time limit exceeded
40	Incorrect	408 ms	34692 KB	Output isn't correct
41	Execution timed out	1065 ms	36356 KB	Time limit exceeded
42	Correct	327 ms	33272 KB	Output is correct
43	Runtime error	785 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
44	Runtime error	490 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Runtime error	284 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
46	Incorrect	343 ms	35264 KB	Output isn't correct
47	Runtime error	842 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	416 ms	36600 KB	Output isn't correct
49	Execution timed out	1070 ms	124644 KB	Time limit exceeded
50	Runtime error	659 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Runtime error	994 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
52	Runtime error	555 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Runtime error	372 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Execution timed out	1051 ms	35320 KB	Time limit exceeded