제출 #153714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153714		brcode	Pipes (BOI13_pipes)	C++14	65 / 100	1086 ms	32484 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];
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 / 30
• Subtask 2: 35 / 70