oj.uz

Submission #153708

# Submission time Handle Problem Language Result Execution time Memory
153708 2019-09-15T09:18:41 Z brcode Pipes (BOI13_pipes) C++14
9.07407 / 100
 1000 ms 131080 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){
        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;
    }
    if(n==2){
        if(val[1]==val[2]){
            cout<<2*val[1]<<endl;
            return 0;
        }
        cout<<0<<endl;
        return 0;
    }
    int root =1;
    while(v1[root].size()==1){
        root++;
        
    }
    
    dfs(root,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 12096 KB Output isn't correct
2 Incorrect 13 ms 12152 KB Output isn't correct
3 Incorrect 15 ms 12360 KB Output isn't correct
4 Incorrect 504 ms 33752 KB Output isn't correct
5 Incorrect 13 ms 12152 KB Output isn't correct
6 Incorrect 13 ms 12096 KB Output isn't correct
7 Incorrect 13 ms 12152 KB Output isn't correct
8 Incorrect 16 ms 12152 KB Output isn't correct
9 Incorrect 16 ms 12280 KB Output isn't correct
10 Incorrect 18 ms 12252 KB Output isn't correct
11 Incorrect 17 ms 12280 KB Output isn't correct
12 Incorrect 15 ms 12280 KB Output isn't correct
13 Incorrect 335 ms 29300 KB Output isn't correct
14 Incorrect 409 ms 32680 KB Output isn't correct
15 Incorrect 413 ms 33964 KB Output isn't correct
16 Incorrect 393 ms 30876 KB Output isn't correct
17 Incorrect 437 ms 33840 KB Output isn't correct
18 Incorrect 444 ms 34004 KB Output isn't correct
19 Incorrect 709 ms 35000 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 522 ms 33884 KB Output isn't correct
23 Incorrect 328 ms 29448 KB Output isn't correct
24 Incorrect 422 ms 33904 KB Output isn't correct
25 Incorrect 355 ms 30200 KB Output isn't correct

Subtask #2
9.07407407407 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 15 ms 12280 KB Output isn't correct
3 Correct 370 ms 33484 KB Output is correct
4 Runtime error 1030 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 460 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 415 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 131 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 179 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 120 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 122 ms 131076 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 120 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 133 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Incorrect 15 ms 12280 KB Output isn't correct
16 Runtime error 178 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 15 ms 12332 KB Output is correct
18 Runtime error 276 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 14 ms 12280 KB Output is correct
20 Runtime error 122 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 128 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 698 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Execution timed out 1066 ms 35032 KB Time limit exceeded
25 Correct 375 ms 33544 KB Output is correct
26 Correct 399 ms 33492 KB Output is correct
27 Runtime error 633 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 381 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 413 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Execution timed out 1070 ms 35924 KB Time limit exceeded
31 Incorrect 996 ms 36072 KB Output isn't correct
32 Execution timed out 1071 ms 108920 KB Time limit exceeded
33 Runtime error 843 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 546 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Execution timed out 1073 ms 116148 KB Time limit exceeded
36 Execution timed out 1071 ms 99088 KB Time limit exceeded
37 Runtime error 418 ms 131080 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Execution timed out 1074 ms 34424 KB Time limit exceeded
39 Execution timed out 1083 ms 112588 KB Time limit exceeded
40 Execution timed out 1078 ms 35036 KB Time limit exceeded
41 Execution timed out 1061 ms 36380 KB Time limit exceeded
42 Correct 336 ms 33308 KB Output is correct
43 Runtime error 805 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Runtime error 464 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Runtime error 296 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Incorrect 424 ms 35324 KB Output isn't correct
47 Runtime error 851 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 413 ms 36464 KB Output isn't correct
49 Execution timed out 1069 ms 124616 KB Time limit exceeded
50 Runtime error 854 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Execution timed out 1073 ms 124884 KB Time limit exceeded
52 Runtime error 548 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 329 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Execution timed out 1076 ms 35044 KB Time limit exceeded