Submission #153713

#	Time	Username	Problem	Language	Result	Execution time	Memory
153713		brcode	Pipes (BOI13_pipes)	C++14	74.07 / 100	718 ms	32036 KiB

pipes

#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];
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);
        }
    }
    
}
int main(){
    long long n,m;
    cin>>n>>m;
    if(m>=n){
        cout<<0<<endl;
        return 0;
    }
    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;
    }
    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 / 30
• Subtask 2: 44.074074074074076 / 70