oj.uz

Submission #153717

# Submission time Handle Problem Language Result Execution time Memory
153717 2019-09-15T10:59:51 Z brcode Pipes (BOI13_pipes) C++14
65 / 100
 775 ms 32400 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(){
    bool ok = false;
    int x1,y1;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        
        v1[x].push_back(y);
        v1[y].push_back(x);
        if(!ok){
            ok = true;
            x1 = x;
            y1= y;
        }
    }
    int curr = 1;
    vector<long long> hold;
    hold.push_back(x1);
   
    visited[x1] = true;
    curr = y1;
    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] = 0;
    for(int i=0;i<n;i++){
        ans[0]+=val[hold[i]];
        if(i%2){
            ans[0]-=2*val[hold[i]];
        }
    }
 
        ans[0]/=2;
      
        for(int i=1;i<=n;i++){
            
            ans[i] = val[hold[i-1]]-ans[i-1];
        }
      
        for(int i=1;i<=n;i++){
            cout<<ans[i]*2<<endl;
            
        }
        //cout<<ans[1]*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;
    }
}

Compilation message

pipes.cpp: In function 'void solve()':
pipes.cpp:32:12: warning: 'y1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,y1;
            ^~
pipes.cpp:47:19: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     hold.push_back(x1);
     ~~~~~~~~~~~~~~^~~~

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 5368 KB Output is correct
4 Correct 688 ms 29172 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 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 5368 KB Output is correct
11 Correct 11 ms 5368 KB Output is correct
12 Correct 12 ms 5408 KB Output is correct
13 Correct 562 ms 24532 KB Output is correct
14 Correct 775 ms 27996 KB Output is correct
15 Correct 718 ms 29308 KB Output is correct
16 Correct 576 ms 25756 KB Output is correct
17 Correct 700 ms 29040 KB Output is correct
18 Correct 711 ms 29344 KB Output is correct
19 Correct 724 ms 32400 KB Output is correct
20 Correct 7 ms 5112 KB Output is correct
21 Correct 11 ms 5240 KB Output is correct
22 Correct 713 ms 29248 KB Output is correct
23 Correct 537 ms 24292 KB Output is correct
24 Correct 733 ms 29132 KB Output is correct
25 Correct 582 ms 25144 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Incorrect 11 ms 5112 KB Output isn't correct
3 Runtime error 181 ms 19776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 5112 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 5032 KB Output isn't correct
9 Incorrect 6 ms 4984 KB Output isn't correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5112 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 10 ms 5112 KB Output isn't correct
16 Incorrect 11 ms 5112 KB Output isn't correct
17 Incorrect 10 ms 5112 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 4984 KB Output is correct
21 Correct 6 ms 5004 KB Output is correct
22 Incorrect 10 ms 5112 KB Output isn't correct
23 Runtime error 155 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 188 ms 20728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 177 ms 19784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 7 ms 5112 KB Output is correct
27 Correct 6 ms 5112 KB Output is correct
28 Correct 6 ms 5112 KB Output is correct
29 Correct 6 ms 5112 KB Output is correct
30 Runtime error 194 ms 20532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 186 ms 20076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 198 ms 20728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 192 ms 20216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Correct 7 ms 4984 KB Output is correct
35 Correct 7 ms 5112 KB Output is correct
36 Correct 7 ms 5112 KB Output is correct
37 Correct 7 ms 5112 KB Output is correct
38 Runtime error 187 ms 20164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 207 ms 20544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 195 ms 20256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 196 ms 19836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Correct 7 ms 4988 KB Output is correct
43 Correct 7 ms 5112 KB Output is correct
44 Correct 8 ms 5112 KB Output is correct
45 Correct 7 ms 4984 KB Output is correct
46 Runtime error 200 ms 19732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 188 ms 20092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 186 ms 19832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 192 ms 20088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Correct 8 ms 5112 KB Output is correct
51 Correct 6 ms 5112 KB Output is correct
52 Correct 6 ms 5112 KB Output is correct
53 Correct 7 ms 5112 KB Output is correct
54 Runtime error 188 ms 20344 KB Execution killed with signal 11 (could be triggered by violating memory limits)