Submission #383225

#	Time	Username	Problem	Language	Result	Execution time	Memory
383225		fammo	Pipes (BOI13_pipes)	C++11	96.11 / 100	186 ms	26212 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], seen[N];
int S = -1, sz = 0;
void markcyc(int v, int u){//cyc u --- v(-backedge-)u
    if(h[u] < h[v])swap(u,v);
    seen[v] = 1;
    while(u != v){
        seen[u] = 1;
        cyc[edg[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;
}
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;
}
void dfs(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];
        if(!mark[u])dfs(u,ed);
        a[v] -= ans[ed];
    }
    if(id != -1 && !seen[v])ans[id] = a[v], a[v] = 0;
    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);
        ind[u].pb(i), ind[v].pb(i);
    }
    if(m == n - 1) solvetree();
    ////////////////////////////////////////////////////////////////////////////////
    /// \brief findcyc
    pre(0);
    for(int i = 0; i < n; i ++)mark[i] = 0;
    findcyc(0);int root = 0;
    for(int i = 0;i < n; i ++){mark[i] = 0; if((int)adj[i].size() != 1)root = i;}
    dfs(root);

    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;

}

/*13 13
3 7 6 8 -2 -4 12 -5 17 -6 1 0 3
1 2
2 3
3 5
5 9
9 8
5 13
13 10
13 7
7 11
11 12
11 6
7 4
4 3*/

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