Submission #677851

#	Time	Username	Problem	Language	Result	Execution time	Memory
677851		dooompy	Pipes (BOI13_pipes)	C++17	100 / 100	119 ms	18288 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[500005];

set<int> adj[100005];
ll calc[500005];
int en[500005], out[500005];

vector<pair<int, int>> ord;

void dfs(int cur, int p, int root) {

    int idx = *adj[cur].begin();

    int nxtidx = (en[idx] == cur ? out[idx] : en[idx]);

    if (nxtidx == p) {
        idx = *adj[cur].rbegin();

        nxtidx = (en[idx] == cur ? out[idx] : en[idx]);
    }

    ord.push_back({cur, idx});

    if (nxtidx != root) dfs(nxtidx, cur, root);
}

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;
        en[i] = a, out[i] = b;
        adj[a].insert(i);
        adj[b].insert(i);
    }

    queue<int> q;

    for (int i = 1; i <= n; i++) {
            q.push(i);

    }

    while (!q.empty()) {
        // deg 1
        auto cur = q.front(); q.pop();

        if (adj[cur].size() == 1) {
            int idx = *adj[cur].begin();

            int nxtidx = (en[idx] == cur ? out[idx] : en[idx]);
            ll weight = v[cur];

            v[nxtidx] -= v[cur];
            v[cur] -= v[cur];

            calc[idx] = 2LL * weight;

            adj[cur].erase(idx);
            adj[nxtidx].erase(idx);

            if (adj[nxtidx].size() == 1) q.push(nxtidx);
        }
    }

    int ct = 0;

    for (int i = 1; i <= n; i++) {
        if (adj[i].size() > 2) {
            cout << 0;
            return 0;
        }

        ct += (adj[i].size() == 2);
    }

    if (ct % 2 == 0 && ct > 0) {
        cout << 0;
        return 0;
    }

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

    dfs(left, -1, left);

//    assert(ord.size() == left.size());

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

    ll prev = 0;

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

        prev = 2LL * v[ord[i].first] - prev;

    }

    ll x = (2LL * v[ord[0].first] - prev) / 2;

//    cout << x << endl;

    calc[ord[0].second] = x;

    for (int i = 1; i < ord.size(); i++) {
        calc[ord[i].second] = 2LL * v[ord[i].first] - calc[ord[i-1].second];
    }


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

Compilation message (stderr)

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

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