oj.uz

Submission #153712

# Submission time Handle Problem Language Result Execution time Memory
153712 2019-09-15T10:17:54 Z brcode Pipes (BOI13_pipes) C++14
65 / 100
 779 ms 113048 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;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 11 ms 5240 KB Output is correct
4 Correct 692 ms 29124 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 11 ms 5240 KB Output is correct
10 Correct 11 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 566 ms 24368 KB Output is correct
14 Correct 735 ms 27864 KB Output is correct
15 Correct 737 ms 29280 KB Output is correct
16 Correct 587 ms 25780 KB Output is correct
17 Correct 710 ms 29036 KB Output is correct
18 Correct 705 ms 29292 KB Output is correct
19 Correct 740 ms 32528 KB Output is correct
20 Correct 7 ms 4984 KB Output is correct
21 Correct 13 ms 5240 KB Output is correct
22 Correct 721 ms 29236 KB Output is correct
23 Correct 565 ms 24188 KB Output is correct
24 Correct 705 ms 29152 KB Output is correct
25 Correct 578 ms 25308 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 29944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 9 ms 5372 KB Output isn't correct
3 Incorrect 664 ms 30148 KB Output isn't correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Runtime error 43 ms 29816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 60 ms 35576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 7 ms 5112 KB Output isn't correct
10 Correct 7 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 Runtime error 88 ms 29700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 8 ms 5368 KB Output isn't correct
16 Runtime error 52 ms 30456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 12 ms 5244 KB Output isn't correct
18 Correct 7 ms 5112 KB Output is correct
19 Correct 6 ms 5112 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 7 ms 5112 KB Output is correct
22 Incorrect 8 ms 5240 KB Output isn't correct
23 Runtime error 383 ms 95896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Incorrect 453 ms 31792 KB Output isn't correct
25 Incorrect 650 ms 30116 KB Output isn't correct
26 Correct 6 ms 4984 KB Output is correct
27 Correct 6 ms 4984 KB Output is correct
28 Correct 6 ms 4984 KB Output is correct
29 Correct 6 ms 4984 KB Output is correct
30 Incorrect 437 ms 34436 KB Output isn't correct
31 Incorrect 497 ms 34236 KB Output isn't correct
32 Runtime error 441 ms 73464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 461 ms 110872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Correct 8 ms 5112 KB Output is correct
35 Correct 6 ms 4984 KB Output is correct
36 Correct 7 ms 5084 KB Output is correct
37 Correct 6 ms 4984 KB Output is correct
38 Incorrect 441 ms 31168 KB Output isn't correct
39 Runtime error 454 ms 76612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Incorrect 449 ms 31048 KB Output isn't correct
41 Incorrect 779 ms 35292 KB Output isn't correct
42 Correct 8 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 6 ms 5084 KB Output is correct
46 Incorrect 469 ms 33204 KB Output isn't correct
47 Runtime error 471 ms 113048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Incorrect 450 ms 35000 KB Output isn't correct
49 Runtime error 438 ms 70904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Correct 6 ms 4984 KB Output is correct
51 Correct 6 ms 5112 KB Output is correct
52 Correct 6 ms 5112 KB Output is correct
53 Correct 6 ms 5112 KB Output is correct
54 Incorrect 447 ms 32336 KB Output isn't correct