Submission #631404

#	Time	Username	Problem	Language	Result	Execution time	Memory
631404		socpite	Pipes (BOI13_pipes)	C++17	75.37 / 100	133 ms	131072 KiB

pipes

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int maxn = 1e5+5;

typedef long long ll;

ll lim = 1;

int _s, _t;

int n, m;
vector<int> idx, vert;

int vis[maxn], oncyc[maxn];
ll val[maxn], ans[maxn], A[maxn];
vector<pair<int, int>> graph[maxn];

void find_ep(int x, int p){
    assert(!vis[x]);
    vis[x]=1;
    for(auto v: graph[x]){
        if(v.f == p)continue;
        if(vis[v.f]){
            if(!_s){
                _s = x;
                _t = v.f;
                idx.push_back(v.s);
            }
        }
        else find_ep(v.f, x);
    }
}

void find_cyc(int x, int p){
    if(x == _t)oncyc[x]=1;
    else{
        for(auto v: graph[x]){
            if(v.f == p || (x == _s && v.f == _t) || (x == _t && v.f == _s))continue;
            find_cyc(v.f, x);
            if(oncyc[v.f]){
                idx.push_back(v.s);
                oncyc[x]=1;
                break;
            }
        }
    }
    if(oncyc[x])vert.push_back(x);
}

void solve(int x, int p){
    for(auto v: graph[x]){
        if(v.f == p || oncyc[v.f])continue;
        solve(v.f, p);
        ans[v.s]=val[v.f];
        val[x]-=val[v.f];
    }
}

void dfs(int x, int p){
    //cout << x << endl;
    for(auto v: graph[x]){
        if(v.f == p)continue;
        dfs(v.f, x);
        ans[v.s]=val[v.f];
        val[x]-=val[v.f];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    if(m > n){
        cout << 0;
        return 0;
    }
    for(int i = 1; i <= n; i++)cin >> val[i];
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }
    if(m == n){
        find_ep(1, 0);
        find_cyc(_s, 0);
        if(!(vert.size()&1)){
            cout << 0;
            return 0;
        }
        assert(vert.size() == idx.size());
        ll sum = 0;
        for(auto v: vert){
            solve(v, 0);
            sum += val[v];
        }
        sum/=2;
        for(int i = 1; i < vert.size(); i+=2)sum-=val[vert[i]];
        ans[idx[0]] = sum;
        for(int i = 1; i < idx.size(); i++)ans[idx[i]] = val[vert[i-1]]-ans[idx[i-1]];
    }
    else{
        dfs(1, 0);
    }
    for(int i = 1; i <= m; i++)cout << ans[i]*2 << "\n";

}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i = 1; i < vert.size(); i+=2)sum-=val[vert[i]];
      |                        ~~^~~~~~~~~~~~~
pipes.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i = 1; i < idx.size(); i++)ans[idx[i]] = val[vert[i-1]]-ans[idx[i-1]];
      |                        ~~^~~~~~~~~~~~

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