oj.uz

Submission #153714

# Submission time Handle Problem Language Result Execution time Memory
153714 2019-09-15T10:38:58 Z brcode Pipes (BOI13_pipes) C++14
65 / 100
 1000 ms 32484 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 719 ms 28992 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 5244 KB Output is correct
10 Correct 11 ms 5240 KB Output is correct
11 Correct 11 ms 5368 KB Output is correct
12 Correct 12 ms 5372 KB Output is correct
13 Correct 551 ms 24300 KB Output is correct
14 Correct 681 ms 27924 KB Output is correct
15 Correct 730 ms 29236 KB Output is correct
16 Correct 603 ms 25748 KB Output is correct
17 Correct 754 ms 29172 KB Output is correct
18 Correct 759 ms 29452 KB Output is correct
19 Correct 739 ms 32484 KB Output is correct
20 Correct 8 ms 5112 KB Output is correct
21 Correct 11 ms 5212 KB Output is correct
22 Correct 697 ms 29288 KB Output is correct
23 Correct 573 ms 24244 KB Output is correct
24 Correct 754 ms 29280 KB Output is correct
25 Correct 642 ms 25340 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4984 KB Output isn't correct
2 Execution timed out 1084 ms 7820 KB Time limit exceeded
3 Incorrect 412 ms 12024 KB Output isn't correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5124 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Incorrect 7 ms 4984 KB Output isn't correct
8 Incorrect 7 ms 5116 KB Output isn't correct
9 Incorrect 8 ms 5112 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 4984 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Incorrect 16 ms 5112 KB Output isn't correct
15 Execution timed out 1059 ms 7808 KB Time limit exceeded
16 Incorrect 15 ms 5112 KB Output isn't correct
17 Incorrect 26 ms 5112 KB Output isn't correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 7 ms 5112 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 6 ms 5112 KB Output is correct
22 Incorrect 716 ms 6760 KB Output isn't correct
23 Execution timed out 1062 ms 12996 KB Time limit exceeded
24 Execution timed out 1061 ms 14152 KB Time limit exceeded
25 Incorrect 425 ms 12004 KB Output isn't correct
26 Correct 6 ms 4984 KB Output is correct
27 Correct 6 ms 5112 KB Output is correct
28 Correct 6 ms 4984 KB Output is correct
29 Correct 6 ms 4984 KB Output is correct
30 Execution timed out 1050 ms 13656 KB Time limit exceeded
31 Execution timed out 1072 ms 13936 KB Time limit exceeded
32 Execution timed out 1078 ms 14568 KB Time limit exceeded
33 Execution timed out 1076 ms 13936 KB Time limit exceeded
34 Correct 6 ms 4984 KB Output is correct
35 Correct 6 ms 5112 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 7 ms 5112 KB Output is correct
38 Execution timed out 1071 ms 14112 KB Time limit exceeded
39 Incorrect 437 ms 12664 KB Output isn't correct
40 Execution timed out 1078 ms 14072 KB Time limit exceeded
41 Execution timed out 1082 ms 13716 KB Time limit exceeded
42 Correct 7 ms 4988 KB Output is correct
43 Correct 6 ms 5112 KB Output is correct
44 Correct 7 ms 5112 KB Output is correct
45 Correct 8 ms 5112 KB Output is correct
46 Execution timed out 1075 ms 14056 KB Time limit exceeded
47 Incorrect 975 ms 13628 KB Output isn't correct
48 Execution timed out 1086 ms 13816 KB Time limit exceeded
49 Incorrect 423 ms 12280 KB Output isn't correct
50 Correct 8 ms 5112 KB Output is correct
51 Correct 7 ms 5112 KB Output is correct
52 Correct 8 ms 5112 KB Output is correct
53 Correct 8 ms 4984 KB Output is correct
54 Execution timed out 1073 ms 13704 KB Time limit exceeded