Submission #444697

#	Time	Username	Problem	Language	Result	Execution time	Memory
444697		Aryan_Raina	Pipes (BOI13_pipes)	C++17	100 / 100	235 ms	40248 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
#define all(a) a.begin(), a.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e15;

void solve() {
    int N, M; cin >> N >> M;
    vector<ar<int,2>> g[N];
    vector<int> C(N), ans(M), degree(N, 0);
    for (int &i : C) cin >> i;

    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        --u, --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        degree[u]++;
        degree[v]++;
    }

    if (M > N) {
        cout << "0\n";
        return;
    }

    queue<int> q;
    for (int i = 0; i < N; i++)
        if (degree[i] == 1) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v,i] : g[u]) if (degree[v]) {
            degree[v]--; degree[u]--;
            C[v] -= (ans[i] = C[u]);
            if (degree[v] == 1) q.push(v);
        }
    }

    if (N-1 == M) {
        for (int i : ans) cout << 2*i << '\n';
        return;
    }

    vector<ar<int,2>> shit;
    for (int x = 0; x < N; x++) if (degree[x] == 2) {
        for (int u = x; u >= 0; ) {
            int nex = -1;
            for (auto [v,i] : g[u]) if (degree[v] == 2){
                shit.push_back({v, i});
                degree[v]--; degree[u]--;
                nex = v;
                break;
            }
            u = nex;
        }

        for (auto [v, i] : g[x]) if (degree[v] == 1) shit.push_back({x, i});
    }

    int lol = 0;
    for (int i = 0; i < shit.size(); i++) {
        if (i&1) lol -= C[shit[i][0]];
        else lol += C[shit[i][0]];
    }

    if (!(shit.size()&1) || lol&1) {
        cout << "0\n"; 
        return;
    }

    lol /= 2;
    for (int i = 0; i < shit.size(); i++) {
        ans[shit[i][1]] = lol;
        lol = C[shit[i][0]] - lol;
    }

    for (int i : ans) cout << 2*i << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
 
    int t = 1; //cin >> t;
    while (t--) solve();   
}  

Compilation message (stderr)

pipes.cpp: In function 'void solve()':
pipes.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < shit.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
pipes.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < shit.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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