Submission #383228

#	Time	Username	Problem	Language	Result	Execution time	Memory
383228		fammo	Pipes (BOI13_pipes)	C++11	74.07 / 100	287 ms	30192 KiB

pipes

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

#define endl '\n'
//#define int long long
const int  N = 100 * 1000 + 20, L = 20, M = 100 * 1000 + 20;////////////////ya5e5
int n, m, c[N], ans[M], a[N], h[N], par[N];
vector<int>adj[N], ind[N];
int edg[N];
void dfst(int v, int p){
    int id = -1;
    for(int i = 0; i < (int)adj[v].size(); i ++){
        int u = adj[v][i], ed = ind[v][i];
        if(u == p){id = ed; continue;}
        dfst(u, v);
        a[v] -= ans[ed];
    }
    if(id!= -1)ans[id] = a[v], a[v] = 0;
}
void solvetree(){
    dfst(0, -1);
    for(int i = 0; i < n; i ++)if(a[i] != 0){cout << 0 << endl; exit(0);}
    for(int i = 0; i < m; i ++)cout << ans[i] << endl;
    exit(0);
}
bool mark[N], dead[M], cyc[M], leaf[N];
int S = -1, deg[N], sz = 0;
void markcyc(int v, int u){//cyc u --- v(-backedge-)u
    if(h[u] < h[v])swap(u,v);
    while(u != v){
        cyc[edg[par[u]]] = 1;
        u = par[u];
    }return;
}
void pre(int v, int id = -1){
    mark[v] = 1;
    for(int i = 0; i < (int)adj[v].size() ; i ++){
        int u = adj[v][i], ed = ind[v][i];
        //cout << "ADJ " << u << " VIA " << ed << endl;
        if(ed == id)continue;
        if(!mark[u]){
            par[u] = v;
            h[u] = h[v] + 1;
            pre(u, ed);
        }
    }
    edg[v] = id;return;
}
void findcyc(int v, int id = -1){
   // cout << "HERE " << v << " FROM " << id << endl;
    mark[v] = 1;
    for(int i = 0; i < (int)adj[v].size() ; i ++){
        int u = adj[v][i], ed = ind[v][i];
        //cout << "ADJ " << u << " VIA " << ed << endl;
        if(ed == id)continue;
        if(mark[u]){
            if((h[v] - h[u])%2){
               // cout << "h" <<v << " -h" << u << " = " << h[v] -h[u] << endl;
                cout << 0 << endl;
                exit(0);
            }
            cyc[ed] = 1;
            S=v;sz = abs(h[u]-h[v])+1;
            markcyc(v,u);
        }else{
            par[u] =v;
            h[u] = h[v] + 1;
            findcyc(u, ed);
        }
    }
    return;
}
int32_t main(){
    fastio;
    ///auto t = clock();
    cin >> n >> m;
    if(m > n) return cout << 0 << endl, 0;
    for(int i = 0; i < n; i ++)cin >> c[i], a[i] = c[i]*2;
    for(int i = 0; i < m; i ++){
        int u, v; cin >> u >> v;
        u --; v --;
        adj[u].pb(v), adj[v].pb(u);deg[u] ++, deg[v] ++;
        ind[u].pb(i), ind[v].pb(i);
    }
    if(m == n - 1) solvetree();
    ////////////////////////////////////////////////////////////////////////////////
    pre(0);
    for(int i = 0; i < n; i ++)mark[i] = 0;
    findcyc(0);
    set<pii>s;
    for(int i= 0; i < n; i ++)s.insert({deg[i], i});
    while(!s.empty()){
        auto it = s.begin();
        int d = it->X, v = it->Y;
        s.erase(s.begin());
        if(d > 1)break;
        for(int i= 0;i  < (int)adj[v].size() ; i ++){
            int u= adj[v][i], ed = ind[v][i]; pii pr ={deg[u], u};
            if(s.find(pr) != s.end()){
                s.erase(pr);deg[u] --;
                s.insert({deg[u],u});
                ans[ed]= a[v]; a[v] = 0;
                a[u]-=ans[ed];
                break;
            }
        }
    }
    vector<int>vec;
    int cur = S, pr = -1;
    for(int t = 0; t < sz; t ++){
        for(int i = 0; i < (int)adj[cur].size(); i ++){
            int u = adj[cur][i], ed =ind[cur][i];
            if(cyc[ed] && u != pr){
                vec.pb(ed);
                if(pr == -1){
                    ans[ed] = 0;
                }else{
                    ans[ed] = a[cur];
                    a[cur]=0;
                    a[u]-=ans[ed];
                }pr= cur; cur = u;goto hell;
            }
        }
        hell:;
    }
    //cout << "S : " << S << ": " << a[S] << endl;
    int df = a[S]/2;
    ans[vec[0]] = df;
    for(int i = 1; i < (int)vec.size(); i ++){ans[vec[i]] -= df; df*=-1;}

    for(int i = 0; i < m; i ++)cout << ans[i] << '\n';
    ///cout << clock() - t << "ms" << endl;
    return 0;

}

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