Submission #677797

#	Time	Username	Problem	Language	Result	Execution time	Memory
677797		dooompy	Pipes (BOI13_pipes)	C++17	74.07 / 100	70 ms	9848 KiB

pipes

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

ll v[100005];
int deg[100005];

vector<pair<int, int>> adj[100005];
ll calc[500005];

bool seen[100005];

bool seen2[100005];
vector<int> ord;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("test.txt", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;

    if (m > n) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        deg[a]++; deg[b]++;
    }

    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        // deg 1
        auto cur = q.front(); q.pop();
        seen[cur] = true;
        deg[cur] = 0;

        for (auto to : adj[cur]) {
            if (seen[to.first]) continue;
            ll weight = v[cur];

            v[to.first] -= weight;
            calc[to.second] = weight;

            if (--deg[to.first] == 1) {
                q.push(to.first);
            }
        }
    }

    if (m == n - 1) {
        for (int i = 1; i <= m; i++) {
            cout << calc[i] * 2 << "\n";
        }
        return 0;
    }

    vector<int> left;

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 2) left.push_back(i);
    }

    if (left.size() % 2 == 0) {
        cout << 0 << endl;
        return 0;
    }

    if (left.empty()) {
        // wtf
        cout << 0 << endl;
        return 0;
    }

    int start = left.front();
    ord.push_back(start);
    seen2[start] = true;
    int cur = start;
    while (true) {
        bool pushed = false;
        for (auto nxt : adj[cur]) {
            if (!seen2[nxt.first] && deg[nxt.first] == 2) {
                cur = nxt.first;
                pushed = true;
                seen2[nxt.first] = true;
                ord.push_back(nxt.first);
                break;
            }
        }
        if (!pushed) break;

    }

//    for (auto x : ord) cout << x << " ";

    ll prev = 0;

    for (int i = 0; i < ord.size() - 1; i++) {
        // assum back ->0 is X

        ll now = v[ord[i]] - prev;

        prev = now;
    }

    ll x = (v[ord[0]] - prev) / 2;

//    cout << x << endl;

    ll orig = x;

    for (int i = 0; i < ord.size() - 1; i++) {
        for (auto nxt : adj[ord[i]]) {
            if (nxt.first == ord[i + 1]) {
                calc[nxt.second] = v[ord[i]] - x;
                x = calc[nxt.second];
                break;
            }
        }
    }

    for (auto nxt : adj[ord[0]]) {
        if (nxt.first == ord.back()) {
            calc[nxt.second] = orig;
            break;
        }
    }

    for (int i = 1; i <= m; i++) {
        cout << calc[i] * 2 << "\n";
    }
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i = 0; i < ord.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~
pipes.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i = 0; i < ord.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~

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