oj.uz

Submission #677833

# Submission time Handle Problem Language Result Execution time Memory
677833 2023-01-04T12:25:23 Z dooompy Pipes (BOI13_pipes) C++17
44.0741 / 100
 143 ms 19524 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[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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Incorrect 4 ms 5040 KB Output isn't correct
3 Incorrect 5 ms 5048 KB Output isn't correct
4 Incorrect 96 ms 17420 KB Output isn't correct
5 Incorrect 3 ms 4948 KB Output isn't correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Incorrect 4 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Incorrect 4 ms 5076 KB Output isn't correct
10 Incorrect 5 ms 5076 KB Output isn't correct
11 Incorrect 5 ms 5168 KB Output isn't correct
12 Incorrect 4 ms 5168 KB Output isn't correct
13 Incorrect 72 ms 15076 KB Output isn't correct
14 Incorrect 100 ms 16868 KB Output isn't correct
15 Incorrect 100 ms 17492 KB Output isn't correct
16 Incorrect 103 ms 15816 KB Output isn't correct
17 Incorrect 106 ms 17408 KB Output isn't correct
18 Incorrect 99 ms 17476 KB Output isn't correct
19 Incorrect 74 ms 17276 KB Output isn't correct
20 Incorrect 4 ms 4948 KB Output isn't correct
21 Incorrect 3 ms 5168 KB Output isn't correct
22 Incorrect 143 ms 17484 KB Output isn't correct
23 Incorrect 78 ms 15144 KB Output isn't correct
24 Incorrect 96 ms 17436 KB Output isn't correct
25 Incorrect 72 ms 15532 KB Output isn't correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Incorrect 4 ms 5204 KB Output isn't correct
3 Correct 74 ms 16848 KB Output is correct
4 Correct 3 ms 5044 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Correct 3 ms 5032 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5032 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Incorrect 3 ms 5168 KB Output isn't correct
16 Incorrect 4 ms 5076 KB Output isn't correct
17 Correct 3 ms 5164 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5044 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Incorrect 4 ms 5076 KB Output isn't correct
23 Incorrect 85 ms 16832 KB Output isn't correct
24 Incorrect 99 ms 19048 KB Output isn't correct
25 Correct 85 ms 17020 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 3 ms 5040 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 3 ms 5076 KB Output is correct
30 Incorrect 83 ms 18688 KB Output isn't correct
31 Incorrect 83 ms 19520 KB Output isn't correct
32 Incorrect 111 ms 18504 KB Output isn't correct
33 Correct 76 ms 17568 KB Output is correct
34 Correct 2 ms 5076 KB Output is correct
35 Correct 2 ms 5084 KB Output is correct
36 Correct 3 ms 5052 KB Output is correct
37 Correct 2 ms 5080 KB Output is correct
38 Incorrect 87 ms 18992 KB Output isn't correct
39 Incorrect 100 ms 18392 KB Output isn't correct
40 Incorrect 108 ms 19032 KB Output isn't correct
41 Correct 57 ms 17768 KB Output is correct
42 Correct 3 ms 5076 KB Output is correct
43 Correct 2 ms 5076 KB Output is correct
44 Correct 3 ms 5076 KB Output is correct
45 Correct 3 ms 4988 KB Output is correct
46 Incorrect 96 ms 18856 KB Output isn't correct
47 Incorrect 99 ms 19088 KB Output isn't correct
48 Incorrect 81 ms 19524 KB Output isn't correct
49 Correct 90 ms 16664 KB Output is correct
50 Correct 3 ms 5076 KB Output is correct
51 Correct 3 ms 5080 KB Output is correct
52 Correct 3 ms 5080 KB Output is correct
53 Correct 3 ms 5044 KB Output is correct
54 Incorrect 86 ms 18640 KB Output isn't correct