Submission #677833

#	Time	Username	Problem	Language	Result	Execution time	Memory
677833		dooompy	Pipes (BOI13_pipes)	C++17	44.07 / 100	143 ms	19524 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];

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

bool seen[100005];

bool seen2[100005];
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++) {
        if (adj[i].size() == 1) {
            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];

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

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

    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 (adj[i].size() == 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();

    dfs(left.front(), -1, left.front());

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

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

    ll prev = 0;

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

        prev = v[ord[i].first] - prev;

    }

    ll x = (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] = v[ord[i].first] - calc[ord[i-1].second];
    }


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

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:96:16: warning: unused variable 'weight' [-Wunused-variable]
   96 |             ll weight = v[cur];
      |                ^~~~~~
pipes.cpp:142: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]
  142 |     for (int i = 0; i < ord.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~
pipes.cpp:155: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]
  155 |     for (int i = 1; i < ord.size(); i++) {
      |                     ~~^~~~~~~~~~~~
pipes.cpp:132:9: warning: unused variable 'start' [-Wunused-variable]
  132 |     int start = left.front();
      |         ^~~~~

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