Submission #755536

#	Time	Username	Problem	Language	Result	Execution time	Memory
755536		dxz05	Pipes (BOI13_pipes)	C++17	100 / 100	598 ms	81384 KiB

pipes

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 5e5 + 3e2;

set<pair<int, int>> g[N];

int tin[N], low[N], timer = 0;
bool used[N];

bool bridge[N];

void dfs(int v, int p = -1){
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (auto [u, i]: g[v]){
        if (u == p) continue;

        if (!used[u]){
            dfs(u, v);

            low[v] = min(low[v], low[u]);

            if (low[u] > tin[v]){
                bridge[i] = true;
            }
        } else {
            low[v] = min(low[v], tin[u]);
        }
    }

}

int cnt_v, cnt_e;
vector<int> comp;

void dfs2(int v){
    used[v] = true;
    cnt_v++;
    comp.push_back(v);

    for (auto [u, i] : g[v]){
        if (bridge[i]) continue;

        cnt_e++;
        if (!used[u]) dfs2(u);
    }
}

int c[N];
ll ans[N];
void solve(){
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> c[i];

    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        --u, --v;

        g[u].emplace(v, i);
        g[v].emplace(u, i);
    }

    dfs(0);

    int cycles_count = 0;

    vector<int> cycle;

    fill(used, used + n, false);

    for (int i = 0; i < n; i++){
        if (used[i]) continue;

        cnt_v = cnt_e = 0;
        comp.clear();

        dfs2(i);

        if (cnt_v == 1) continue;
        cycle = comp;

        cycles_count++;
        cnt_e /= 2;

        if (cnt_e != cnt_v || cnt_v % 2 == 0 || cycles_count > 1){
            cout << 0 << endl;
            return;
        }

    }

    queue<int> q;
    for (int i = 0; i < n; i++){
        if (g[i].size() == 1) q.push(i);
    }

    while (!q.empty()){
        int v = q.front();
        q.pop();

        if (g[v].size() != 1) continue;

        auto [u, i] = *g[v].begin();
        ans[i] = 2 * c[v];
        c[u] -= c[v];
        g[u].erase(make_pair(v, i));

        if (g[u].size() == 1){
            q.push(u);
        }
    }

    int k = (int) cycle.size();

    if (k > 0) {
        ll tot = 0;
        for (int v : cycle) tot += c[v];

        vector<ll> dp(k, 0);
        for (int i = 0; i + 1 < k; i += 2) dp[0] += c[cycle[i]];
        for (int i = 1; i + 1 < k; i += 2) dp[1] += c[cycle[i]];

        for (int i = 2; i < k; i++){
            dp[i] = dp[i - 2] - c[cycle[i - 2]];
            int j = i + 2 * (k / 2 - 1);
            j %= k;
            dp[i] += c[cycle[j]];
        }

        for (int i = 0; i < k; i++) {
            int v = cycle[i], u = cycle[(i + 1) % k];

            int j = g[v].lower_bound(make_pair(u, 0))->second;
            ans[j] = tot - 2 * dp[(i + 2) % k];
        }
    }

    for (int i = 0; i < m; i++){
        cout << ans[i] << "\n";
    }

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:165:13: warning: unused variable 'startTime' [-Wunused-variable]
  165 |     clock_t startTime = clock();
      |             ^~~~~~~~~

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