oj.uz

Submission #153617

# Submission time Handle Problem Language Result Execution time Memory
153617 2019-09-15T04:23:51 Z brcode Pipes (BOI13_pipes) C++14
10.3704 / 100
 1000 ms 131076 KB 
#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 && curr!=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;
    }
    dfs(1,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

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12280 KB Output isn't correct
2 Incorrect 13 ms 12152 KB Output isn't correct
3 Incorrect 16 ms 12280 KB Output isn't correct
4 Incorrect 452 ms 34032 KB Output isn't correct
5 Incorrect 13 ms 12152 KB Output isn't correct
6 Incorrect 13 ms 12168 KB Output isn't correct
7 Incorrect 13 ms 12168 KB Output isn't correct
8 Incorrect 13 ms 12156 KB Output isn't correct
9 Incorrect 15 ms 12280 KB Output isn't correct
10 Incorrect 15 ms 12280 KB Output isn't correct
11 Incorrect 16 ms 12280 KB Output isn't correct
12 Incorrect 15 ms 12280 KB Output isn't correct
13 Incorrect 341 ms 29556 KB Output isn't correct
14 Incorrect 414 ms 32764 KB Output isn't correct
15 Incorrect 513 ms 34008 KB Output isn't correct
16 Incorrect 364 ms 30804 KB Output isn't correct
17 Incorrect 430 ms 33776 KB Output isn't correct
18 Incorrect 429 ms 33952 KB Output isn't correct
19 Incorrect 683 ms 34936 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 536 ms 34120 KB Output isn't correct
23 Incorrect 413 ms 29424 KB Output isn't correct
24 Incorrect 430 ms 34044 KB Output isn't correct
25 Incorrect 347 ms 30296 KB Output isn't correct

Subtask #2
10.3703703704 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 15 ms 12284 KB Output isn't correct
3 Correct 368 ms 33592 KB Output is correct
4 Execution timed out 1046 ms 131076 KB Time limit exceeded
5 Runtime error 465 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 418 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 134 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 189 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 125 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 125 ms 131072 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 130 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 222 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Incorrect 16 ms 12280 KB Output isn't correct
16 Runtime error 197 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 17 ms 12280 KB Output is correct
18 Runtime error 282 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 15 ms 12280 KB Output is correct
20 Correct 15 ms 12280 KB Output is correct
21 Runtime error 131 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 744 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Execution timed out 1060 ms 35088 KB Time limit exceeded
25 Correct 375 ms 33652 KB Output is correct
26 Correct 449 ms 33324 KB Output is correct
27 Runtime error 818 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 393 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 437 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Execution timed out 1077 ms 35960 KB Time limit exceeded
31 Execution timed out 1080 ms 36268 KB Time limit exceeded
32 Execution timed out 1043 ms 111732 KB Time limit exceeded
33 Runtime error 830 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 544 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Execution timed out 1078 ms 119928 KB Time limit exceeded
36 Execution timed out 1086 ms 99036 KB Time limit exceeded
37 Runtime error 417 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Execution timed out 1079 ms 34572 KB Time limit exceeded
39 Execution timed out 1091 ms 112540 KB Time limit exceeded
40 Incorrect 408 ms 34692 KB Output isn't correct
41 Execution timed out 1065 ms 36356 KB Time limit exceeded
42 Correct 327 ms 33272 KB Output is correct
43 Runtime error 785 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Runtime error 490 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Runtime error 284 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Incorrect 343 ms 35264 KB Output isn't correct
47 Runtime error 842 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 416 ms 36600 KB Output isn't correct
49 Execution timed out 1070 ms 124644 KB Time limit exceeded
50 Runtime error 659 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 994 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
52 Runtime error 555 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 372 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Execution timed out 1051 ms 35320 KB Time limit exceeded