Submission #253725

#	Time	Username	Problem	Language	Result	Execution time	Memory
253725		kimbj0709	Pipes (BOI13_pipes)	C++14	100 / 100	158 ms	22260 KiB

pipes

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
#define f first
#define s second
vector<int> sum(maxn,0);
vector<int> currsum(maxn,0);
bool visited[2][maxn];
vector<int> ans(maxn);
vector<int> degree(maxn,0);
vector<vector<pair<int,int> > > adj(maxn);
void dfs(int node,int parity){
    visited[parity][node] = 1;
    for(auto k:adj[node]){
        if(visited[!parity][k.f]==0){
            dfs(k.f,!parity);
        }
    }
}
void dfs2(int node,vector<int> &curr){
    curr.push_back(node);
    degree[node]--;
    for(auto k:adj[node]){
        if(degree[k.f]==2){
            dfs2(k.f,curr);
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_vertex,no_of_edge;
    int input1,input2;
    cin >> no_of_vertex >> no_of_edge;
    if(no_of_vertex<no_of_edge){
        cout << 0;
        return 0;
    }
    for(int i=1;i<=no_of_vertex;i++){
        cin >> sum[i];
    }
    for(int i=0;i<no_of_edge;i++){
        cin >> input1 >> input2;
        degree[input1]++;
        degree[input2]++;
        adj[input1].push_back({input2,i});
        adj[input2].push_back({input1,i});
    }
    dfs(1,0);
    for(int i=1;i<=no_of_vertex;i++){
        if(visited[0][i]==1&&visited[1][i]==1){
        }
        else if(no_of_edge!=no_of_vertex-1){
            cout << 0;
            return 0;
        }
    }
    deque<int> q1;
    for(int i=1;i<=no_of_vertex;i++){
        if(degree[i]==1){
            q1.push_back(i);
        }
    }
    while(q1.size()!=0){
        int a = q1.front();
        q1.pop_front();
        degree[a]--;
        for(auto k:adj[a]){
            if(degree[k.f]==0){
                continue;
            }
            degree[k.f]--;
            currsum[k.f] += (sum[a]-currsum[a]);
            ans[k.s] = (sum[a]-currsum[a]);
            if(degree[k.f]==1){
                q1.push_back(k.f);
            }
        }
    }
    vector<int> curr;
    for(int i=1;i<=no_of_vertex;i++){
        if(degree[i]==2){
            dfs2(i,curr);
            break;
        }
    }
    if(curr.size()==0){
        for(int i=0;i<no_of_edge;i++){
            cout << ans[i]*2 << "\n";
        }
        return 0;
    }
    int temp = 0;
    for(int i=1;i<curr.size();i++){
        if(i%2==1){
            temp += sum[curr[i]]-currsum[curr[i]];
        }
        else{
            temp -= sum[curr[i]]-currsum[curr[i]];
        }
    }
    int rn = ((sum[curr[0]]-currsum[curr[0]])-temp)/2;
    currsum[curr[0]] += rn;
    currsum[curr[curr.size()-1]]+=rn;
    for(auto k:adj[curr[0]]){
        if(k.f==curr[curr.size()-1]){
            ans[k.s] = rn;
        }
    }
    for(int i=0;i<curr.size()-1;i++){
        int nextval = sum[curr[i]]-currsum[curr[i]];
        for(auto k:adj[curr[i]]){
            if(k.f==curr[i+1]){
                ans[k.s] = nextval;
                currsum[curr[i+1]] += nextval;
            }
        }
    }
    for(int i=0;i<no_of_edge;i++){
        //assert(ans[i]!=0);
        cout << ans[i]*2 << "\n";
    }
 
}

Compilation message (stderr)

pipes.cpp: In function 'int32_t main()':
pipes.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<curr.size();i++){
                 ~^~~~~~~~~~~~
pipes.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<curr.size()-1;i++){
                 ~^~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70