oj.uz

Submission #677842

# Submission time Handle Problem Language Result Execution time Memory
677842 2023-01-04T12:29:06 Z dooompy Pipes (BOI13_pipes) C++17
74.0741 / 100
 129 ms 18836 KB 
#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] = weight;

            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

pipes.cpp: In function 'int main()':
pipes.cpp:140: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]
  140 |     for (int i = 0; i < ord.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~
pipes.cpp:153: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]
  153 |     for (int i = 1; i < ord.size(); i++) {
      |                     ~~^~~~~~~~~~~~
pipes.cpp:130:9: warning: unused variable 'start' [-Wunused-variable]
  130 |     int start = left.front();
      |         ^~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 129 ms 17552 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5048 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 109 ms 14940 KB Output is correct
14 Correct 104 ms 16872 KB Output is correct
15 Correct 112 ms 17632 KB Output is correct
16 Correct 79 ms 15664 KB Output is correct
17 Correct 96 ms 17520 KB Output is correct
18 Correct 109 ms 17548 KB Output is correct
19 Correct 127 ms 17536 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 111 ms 17568 KB Output is correct
23 Correct 92 ms 14984 KB Output is correct
24 Correct 99 ms 17612 KB Output is correct
25 Correct 77 ms 15504 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Incorrect 3 ms 5248 KB Output isn't correct
3 Correct 88 ms 16624 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 4 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4960 KB Output isn't correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Incorrect 5 ms 5204 KB Output isn't correct
16 Incorrect 3 ms 5076 KB Output isn't correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 4972 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Incorrect 3 ms 5076 KB Output isn't correct
23 Incorrect 73 ms 15888 KB Output isn't correct
24 Incorrect 104 ms 18272 KB Output isn't correct
25 Correct 96 ms 16612 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4992 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Incorrect 84 ms 17820 KB Output isn't correct
31 Incorrect 86 ms 18828 KB Output isn't correct
32 Incorrect 91 ms 17676 KB Output isn't correct
33 Correct 107 ms 17344 KB Output is correct
34 Correct 4 ms 4988 KB Output is correct
35 Correct 4 ms 5020 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 3 ms 4948 KB Output is correct
38 Incorrect 97 ms 18220 KB Output isn't correct
39 Incorrect 101 ms 17440 KB Output isn't correct
40 Incorrect 88 ms 18120 KB Output isn't correct
41 Correct 68 ms 17656 KB Output is correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 4 ms 4948 KB Output is correct
44 Correct 4 ms 4948 KB Output is correct
45 Correct 3 ms 4948 KB Output is correct
46 Incorrect 122 ms 18128 KB Output isn't correct
47 Incorrect 98 ms 18208 KB Output isn't correct
48 Incorrect 110 ms 18836 KB Output isn't correct
49 Correct 98 ms 16468 KB Output is correct
50 Correct 3 ms 4948 KB Output is correct
51 Correct 3 ms 4948 KB Output is correct
52 Correct 3 ms 4948 KB Output is correct
53 Correct 3 ms 4948 KB Output is correct
54 Incorrect 129 ms 17844 KB Output isn't correct