답안 #153713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153713 2019-09-15T10:18:54 Z brcode Pipes (BOI13_pipes) C++14
74.0741 / 100
718 ms 32036 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;
    if(m>=n){
        cout<<0<<endl;
        return 0;
    }
    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 5112 KB Output is correct
3 Correct 11 ms 5240 KB Output is correct
4 Correct 700 ms 28996 KB Output is correct
5 Correct 7 ms 4984 KB Output is correct
6 Correct 7 ms 5100 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 11 ms 5240 KB Output is correct
10 Correct 12 ms 5240 KB Output is correct
11 Correct 12 ms 5240 KB Output is correct
12 Correct 12 ms 5276 KB Output is correct
13 Correct 550 ms 24428 KB Output is correct
14 Correct 661 ms 27676 KB Output is correct
15 Correct 702 ms 28920 KB Output is correct
16 Correct 585 ms 25656 KB Output is correct
17 Correct 703 ms 28880 KB Output is correct
18 Correct 718 ms 28912 KB Output is correct
19 Correct 691 ms 32036 KB Output is correct
20 Correct 7 ms 4984 KB Output is correct
21 Correct 11 ms 5240 KB Output is correct
22 Correct 700 ms 29280 KB Output is correct
23 Correct 535 ms 24252 KB Output is correct
24 Correct 697 ms 29064 KB Output is correct
25 Correct 584 ms 25216 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Incorrect 6 ms 5076 KB Output isn't correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Incorrect 6 ms 4984 KB Output isn't correct
8 Incorrect 6 ms 4984 KB Output isn't correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct
13 Correct 7 ms 4984 KB Output is correct
14 Incorrect 6 ms 4984 KB Output isn't correct
15 Incorrect 6 ms 5112 KB Output isn't correct
16 Incorrect 6 ms 5112 KB Output isn't correct
17 Correct 7 ms 5112 KB Output is correct
18 Correct 6 ms 5084 KB Output is correct
19 Correct 6 ms 4984 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 7 ms 4984 KB Output is correct
22 Incorrect 7 ms 5112 KB Output isn't correct
23 Incorrect 6 ms 5112 KB Output isn't correct
24 Incorrect 6 ms 5112 KB Output isn't correct
25 Correct 6 ms 4984 KB Output is correct
26 Correct 7 ms 5112 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Correct 8 ms 5192 KB Output is correct
29 Correct 7 ms 4984 KB Output is correct
30 Incorrect 6 ms 5112 KB Output isn't correct
31 Incorrect 6 ms 4984 KB Output isn't correct
32 Incorrect 6 ms 5112 KB Output isn't correct
33 Correct 6 ms 4984 KB Output is correct
34 Correct 6 ms 4984 KB Output is correct
35 Correct 6 ms 4984 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 6 ms 5112 KB Output is correct
38 Incorrect 6 ms 4984 KB Output isn't correct
39 Incorrect 6 ms 5112 KB Output isn't correct
40 Incorrect 6 ms 4984 KB Output isn't correct
41 Correct 6 ms 4984 KB Output is correct
42 Correct 6 ms 4984 KB Output is correct
43 Correct 6 ms 4984 KB Output is correct
44 Correct 6 ms 4984 KB Output is correct
45 Correct 7 ms 4984 KB Output is correct
46 Incorrect 6 ms 4984 KB Output isn't correct
47 Incorrect 7 ms 5112 KB Output isn't correct
48 Incorrect 6 ms 4984 KB Output isn't correct
49 Correct 7 ms 5112 KB Output is correct
50 Correct 6 ms 4984 KB Output is correct
51 Correct 6 ms 4984 KB Output is correct
52 Correct 6 ms 5112 KB Output is correct
53 Correct 6 ms 4984 KB Output is correct
54 Incorrect 6 ms 4984 KB Output isn't correct