| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 153713 |
2019-09-15T10:18:54 Z |
brcode |
Pipes (BOI13_pipes) |
C++14 |
|
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;
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
