Submission #153708

#	Time	Username	Problem	Language	Result	Execution time	Memory
153708		brcode	Pipes (BOI13_pipes)	C++14	9.07 / 100	1083 ms	131080 KiB

pipes

#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
• Subtask 2: 9.074074074074074 / 70