답안 #153711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153711 2019-09-15T10:08:15 Z brcode Pipes (BOI13_pipes) C++14
35.1852 / 100
1000 ms 131076 KB
#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;
    }
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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