oj.uz

Submission #153715

# Submission time Handle Problem Language Result Execution time Memory
153715 2019-09-15T10:42:57 Z brcode Pipes (BOI13_pipes) C++14
65 / 100
 767 ms 32528 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];
bool visited[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);
        }
    }
    
}    long long n,m;
void solve(){
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
      
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    int curr = 1;
    vector<long long> hold;
    while(!visited[curr]){
       
        visited[curr] = true;
        hold.push_back(curr);
       
        for(int x:v1[curr]){
            if(!visited[x]){
                curr = x;
                
                break;
            }
        }
        if(visited[curr]){
            break;
        }
      
        
        
    }
      ans[0] = val[0];
    for(int i=0;i<n;i++){
            ans[0]+=val[0];
            if(i%2){
                ans[0]-=2*val[i];
            }
        }
        ans[0]/=2;
        for(int i=1;i<=n;i++){
            ans[i] = val[i-1]-ans[i-1];
        }
        for(int i=1;i<=n;i++){
            cout<<ans[i]*2<<endl;
            
        }
}
int main(){

    cin>>n>>m;
    if(m>n){
        cout<<0<<endl;
        return 0;
    }
    
    for(long long i=1;i<=n;i++){
        cin>>val[i];
    }
    if(n==m){
        solve();
        
        return 0;
    }
   
    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 702 ms 28984 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5116 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 11 ms 5244 KB Output is correct
10 Correct 11 ms 5368 KB Output is correct
11 Correct 12 ms 5368 KB Output is correct
12 Correct 11 ms 5368 KB Output is correct
13 Correct 540 ms 24496 KB Output is correct
14 Correct 658 ms 27928 KB Output is correct
15 Correct 700 ms 29336 KB Output is correct
16 Correct 577 ms 25704 KB Output is correct
17 Correct 707 ms 29048 KB Output is correct
18 Correct 767 ms 29296 KB Output is correct
19 Correct 731 ms 32528 KB Output is correct
20 Correct 7 ms 5112 KB Output is correct
21 Correct 11 ms 5340 KB Output is correct
22 Correct 713 ms 29264 KB Output is correct
23 Correct 543 ms 24408 KB Output is correct
24 Correct 705 ms 29224 KB Output is correct
25 Correct 567 ms 25320 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4980 KB Output isn't correct
2 Incorrect 10 ms 5112 KB Output isn't correct
3 Incorrect 423 ms 12104 KB Output isn't correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Incorrect 7 ms 5112 KB Output isn't correct
8 Incorrect 7 ms 5112 KB Output isn't correct
9 Incorrect 7 ms 4984 KB Output isn't correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Incorrect 7 ms 5112 KB Output isn't correct
15 Incorrect 11 ms 5112 KB Output isn't correct
16 Incorrect 10 ms 5116 KB Output isn't correct
17 Incorrect 11 ms 5124 KB Output isn't correct
18 Correct 6 ms 4984 KB Output is correct
19 Correct 7 ms 5112 KB Output is correct
20 Correct 7 ms 4984 KB Output is correct
21 Correct 6 ms 4984 KB Output is correct
22 Incorrect 13 ms 5116 KB Output isn't correct
23 Incorrect 365 ms 11512 KB Output isn't correct
24 Incorrect 465 ms 12320 KB Output isn't correct
25 Incorrect 416 ms 11768 KB Output isn't correct
26 Correct 7 ms 5112 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Correct 6 ms 5116 KB Output is correct
29 Correct 6 ms 5112 KB Output is correct
30 Incorrect 460 ms 11632 KB Output isn't correct
31 Incorrect 440 ms 11612 KB Output isn't correct
32 Incorrect 439 ms 11916 KB Output isn't correct
33 Incorrect 440 ms 11552 KB Output isn't correct
34 Correct 8 ms 5112 KB Output is correct
35 Correct 6 ms 5112 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 6 ms 5112 KB Output is correct
38 Incorrect 441 ms 11888 KB Output isn't correct
39 Incorrect 440 ms 12152 KB Output isn't correct
40 Incorrect 442 ms 11984 KB Output isn't correct
41 Incorrect 447 ms 11640 KB Output isn't correct
42 Correct 6 ms 4984 KB Output is correct
43 Correct 6 ms 5112 KB Output is correct
44 Correct 6 ms 4984 KB Output is correct
45 Correct 6 ms 5112 KB Output is correct
46 Incorrect 443 ms 11500 KB Output isn't correct
47 Incorrect 438 ms 11576 KB Output isn't correct
48 Incorrect 439 ms 11384 KB Output isn't correct
49 Incorrect 414 ms 11512 KB Output isn't correct
50 Correct 6 ms 5084 KB Output is correct
51 Correct 6 ms 5112 KB Output is correct
52 Correct 6 ms 5140 KB Output is correct
53 Correct 7 ms 5112 KB Output is correct
54 Incorrect 445 ms 11592 KB Output isn't correct