답안 #153708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153708	2019-09-15T09:18:41 Z	brcode	Pipes (BOI13_pipes)	C++14	9.07407 / 100	1000 ms	131080 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){
        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;
    }
    if(n==2){
        if(val[1]==val[2]){
            cout<<2*val[1]<<endl;
            return 0;
        }
        cout<<0<<endl;
        return 0;
    }
    int root =1;
    while(v1[root].size()==1){
        root++;
        
    }
    
    dfs(root,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	12096 KB	Output isn't correct
2	Incorrect	13 ms	12152 KB	Output isn't correct
3	Incorrect	15 ms	12360 KB	Output isn't correct
4	Incorrect	504 ms	33752 KB	Output isn't correct
5	Incorrect	13 ms	12152 KB	Output isn't correct
6	Incorrect	13 ms	12096 KB	Output isn't correct
7	Incorrect	13 ms	12152 KB	Output isn't correct
8	Incorrect	16 ms	12152 KB	Output isn't correct
9	Incorrect	16 ms	12280 KB	Output isn't correct
10	Incorrect	18 ms	12252 KB	Output isn't correct
11	Incorrect	17 ms	12280 KB	Output isn't correct
12	Incorrect	15 ms	12280 KB	Output isn't correct
13	Incorrect	335 ms	29300 KB	Output isn't correct
14	Incorrect	409 ms	32680 KB	Output isn't correct
15	Incorrect	413 ms	33964 KB	Output isn't correct
16	Incorrect	393 ms	30876 KB	Output isn't correct
17	Incorrect	437 ms	33840 KB	Output isn't correct
18	Incorrect	444 ms	34004 KB	Output isn't correct
19	Incorrect	709 ms	35000 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	522 ms	33884 KB	Output isn't correct
23	Incorrect	328 ms	29448 KB	Output isn't correct
24	Incorrect	422 ms	33904 KB	Output isn't correct
25	Incorrect	355 ms	30200 KB	Output isn't correct

Subtask #2

9.07407407407 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	138 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Incorrect	15 ms	12280 KB	Output isn't correct
3	Correct	370 ms	33484 KB	Output is correct
4	Runtime error	1030 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	460 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	415 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	131 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	179 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	120 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	122 ms	131076 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	120 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	133 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Incorrect	15 ms	12280 KB	Output isn't correct
16	Runtime error	178 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Correct	15 ms	12332 KB	Output is correct
18	Runtime error	276 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Correct	14 ms	12280 KB	Output is correct
20	Runtime error	122 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Runtime error	128 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	698 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
24	Execution timed out	1066 ms	35032 KB	Time limit exceeded
25	Correct	375 ms	33544 KB	Output is correct
26	Correct	399 ms	33492 KB	Output is correct
27	Runtime error	633 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
28	Runtime error	381 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
29	Runtime error	413 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Execution timed out	1070 ms	35924 KB	Time limit exceeded
31	Incorrect	996 ms	36072 KB	Output isn't correct
32	Execution timed out	1071 ms	108920 KB	Time limit exceeded
33	Runtime error	843 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
34	Runtime error	546 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
35	Execution timed out	1073 ms	116148 KB	Time limit exceeded
36	Execution timed out	1071 ms	99088 KB	Time limit exceeded
37	Runtime error	418 ms	131080 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
38	Execution timed out	1074 ms	34424 KB	Time limit exceeded
39	Execution timed out	1083 ms	112588 KB	Time limit exceeded
40	Execution timed out	1078 ms	35036 KB	Time limit exceeded
41	Execution timed out	1061 ms	36380 KB	Time limit exceeded
42	Correct	336 ms	33308 KB	Output is correct
43	Runtime error	805 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
44	Runtime error	464 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Runtime error	296 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
46	Incorrect	424 ms	35324 KB	Output isn't correct
47	Runtime error	851 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	413 ms	36464 KB	Output isn't correct
49	Execution timed out	1069 ms	124616 KB	Time limit exceeded
50	Runtime error	854 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Execution timed out	1073 ms	124884 KB	Time limit exceeded
52	Runtime error	548 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Runtime error	329 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Execution timed out	1076 ms	35044 KB	Time limit exceeded