Submission #1077758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077758		SoMotThanhXuan	Pipes (BOI13_pipes)	C++17	74.07 / 100	113 ms	44372 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = b; i >= a; --i)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define REPD(i, a, b) for(int i = b; i > a; -- i)
#define ALL(v) v.begin(),v.end()
#define next __next
#define left __left
#define right __right
#define prev __prev
const int MOD[6] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277, 998244353};
const int BASE[6] = {23309, 300, 330, 280, 2309, 256};
const int base = BASE[0];
const int mod = MOD[0];
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
void minimize(int &u, int v){
    if(u > v) u = v;
}
void maximize(int &u, int v){
    if(u < v) u = v;
}
void minimizell(long long &u, long long v){
    if(u > v) u = v;
}
void maximizell(long long &u, long long v){
    if(u < v) u = v;
}
const int maxN = 1e5 + 2;
const int maxM = 5e5 + 2;
const int maxK = 1e2 + 2;
const int INF = 1e9 + 8;
const long long INFLL = 1e18;
const int LOG = 16;
int N, M;
vector<pair<int, int>> adj[maxN];
pair<int, int> edge[maxM];
int deg[maxN];
bool del[maxN];
queue<int> listSource;
int res[maxM], c[maxN];
int st, ed, firstEdge;
int listEdge[maxN];
int node[maxN];
int cnt = 0;
void Dfs1(int u, int p){
    for(pair<int, int> x : adj[u]){
        int v = x.fi;
        if(v != p){
            Dfs1(v, u);
            res[x.second] = 2 * c[v];
            c[u] -= c[v];
        }
    }
}
void Dfs2(int u, int p, int id){
    node[++cnt] = u;
    listEdge[cnt] = id;
    if(u == ed){
        res[firstEdge] = c[st];
        int d = 1;
        FOR(i, 2, cnt){
            res[firstEdge] += d * c[node[i]];
            d *= -1;
        }
        FOR(i, 2, cnt){
            res[listEdge[i]] = 2 * c[node[i - 1]] - res[listEdge[i - 1]];
        }
        FOR(i, 1, M)cout << res[i] << "\n";
        exit(0);
    }
    for(pair<int, int> x : adj[u]){
        int v = x.fi;
        if(v == p)continue;
        Dfs2(v, u, x.second);
    }
    --cnt;
}
int main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    //freopen(".INP", "w", stdout);
    //freopen(".ANS", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    FOR(i, 1, N)cin >> c[i];
    FOR(i, 1, M){
        int u, v;
        cin >> u >> v;
        edge[i] = make_pair(u, v);
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        deg[u]++;
        deg[v]++;
    }
    if(M > N){
        cout << 0;
        return 0;
    }
    if(M == N - 1){
        Dfs1(1, 0);
        FOR(i, 1, M)cout << res[i] << '\n';
        return 0;
    }
    FOR(i, 1, N)if(deg[i] == 1){
        if(deg[i] == 1){
            listSource.push(i);
            del[i] = true;
        }
    }
    while(!listSource.empty()){
        int u = listSource.front();
        listSource.pop();
        for(pair<int, int> x : adj[u]){

            int v = x.fi;
            if(del[v])continue;
            c[v] -= c[u];
            res[x.se] = 2 * c[u];
            deg[v]--;
            if(deg[v] == 1){
                del[v] = true;
                listSource.push(v);
            }
        }
    }
    int cnt = 0;
    FOR(i, 1, N)if(del[i] == 0)++cnt;
    if((cnt & 1) == 0){
        cout << 0;
        return 0;
    }
    FOR(i, 1, M){
        int u = edge[i].fi, v = edge[i].se;
        if(del[u] == false && del[v] == false){
            st = u;
            firstEdge = i;
            break;
        }
    }
    Dfs2(st, ed, firstEdge);

    return 0;
}

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