oj.uz

Submission #1053766

# Submission time Handle Problem Language Result Execution time Memory
1053766 2024-08-11T17:18:47 Z codexistent Pipes (BOI13_pipes) C++14
65 / 100
 273 ms 102480 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
#define MAXM 500005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, m, w[MAXN], d[MAXM];
set<ll> adj[MAXN], adj_id[MAXN];
pair<ll, pair<ll, ll>> e[MAXN];
bool v[MAXM];
map<pair<ll, ll>, ll> eid;

int main(){
    cin >> n >> m;
    FOR(i, 1, n) cin >> w[i];
    FOR(i, 1, m){
        e[i].f = 0;
        cin >> e[i].s.f >> e[i].s.s;
        adj[e[i].s.f].insert(e[i].s.s), adj[e[i].s.s].insert(e[i].s.f);
        adj_id[e[i].s.f].insert(i), adj_id[e[i].s.s].insert(i);

        eid.insert({{min(e[i].s.f, e[i].s.s), max(e[i].s.f, e[i].s.s)}, i});
    }

    priority_queue<pair<ll, ll>> pq;
    FOR(i, 1, m) {
        v[i] = false;
        e[i].f = adj[e[i].s.f].size() + adj[e[i].s.s].size();
        //cout << "FOR EDGE " << i << " WE HAVE " << e[i].f << " CT " << endl;
        for(auto j : adj[e[i].s.f]){
            if(adj[j].size() == 2 && adj[e[i].s.s].find(j) != adj[e[i].s.s].end()){
                e[i].f -= 2;
            }
        }

        if(adj[e[i].s.f].size() == 1 || adj[e[i].s.s].size() == 1){
            pq.push({1, i});
        }else if(e[i].f == 0){
            pq.push({0, i});
        }
    }
    while(pq.size()){
        //cout << pq.top().f << " ~ " << pq.top().s << " ==> " << e[pq.top().s].f << endl;
        auto pqi = pq.top(); pq.pop();
        if(v[pqi.s]) continue;
        v[pqi.s] = true;

        if(pqi.f == 0){
            ll s = 0;
            for(ll i2 : adj[e[pqi.s].s.f]) s += w[i2];
            for(ll i2 : adj[e[pqi.s].s.s]) s += w[i2];

            d[pqi.s] = w[e[pqi.s].s.f] + w[e[pqi.s].s.s] - s;
        }else if(adj[e[pqi.s].s.f].size() == 1){
            d[pqi.s] = w[e[pqi.s].s.f] * 2;
        }else{
            d[pqi.s] = w[e[pqi.s].s.s] * 2;
        }

        adj[e[pqi.s].s.f].erase(e[pqi.s].s.s);
        adj[e[pqi.s].s.s].erase(e[pqi.s].s.f);
        w[e[pqi.s].s.f] -= d[pqi.s] / 2;
        w[e[pqi.s].s.s] -= d[pqi.s] / 2;

        if(adj[e[pqi.s].s.f].size() == 2){
            ll a = *(adj[e[pqi.s].s.f].begin());
            ll b = *(++adj[e[pqi.s].s.f].begin());

            if(eid.find({min(a, b), max(a, b)}) != eid.end()){
                e[eid[{min(a, b), max(a, b)}]].f -= 2;

                if(!v[eid[{min(a, b), max(a, b)}]] && e[eid[{min(a, b), max(a, b)}]].f == 0){
                    pq.push({0, eid[{min(a, b), max(a, b)}]});
                }
            }
        }else if(adj[e[pqi.s].s.f].size() == 1){
            ll a = *(adj[e[pqi.s].s.f].begin());
            if(!v[eid[{min(a, e[pqi.s].s.f), max(a, e[pqi.s].s.f)}]]){
                pq.push({1, eid[{min(a, e[pqi.s].s.f), max(a, e[pqi.s].s.f)}]});
            }
        }

        if(adj[e[pqi.s].s.s].size() == 2){
            ll a = *(adj[e[pqi.s].s.s].begin());
            ll b = *(++adj[e[pqi.s].s.s].begin());

            if(eid.find({min(a, b), max(a, b)}) != eid.end()){
                e[eid[{min(a, b), max(a, b)}]].f -= 2;

                if(!v[eid[{min(a, b), max(a, b)}]] && e[eid[{min(a, b), max(a, b)}]].f == 0){
                    pq.push({0, eid[{min(a, b), max(a, b)}]});
                }
            }
        }else if(adj[e[pqi.s].s.s].size() == 1){
            ll a = *(adj[e[pqi.s].s.s].begin());
            if(!v[eid[{min(a, e[pqi.s].s.s), max(a, e[pqi.s].s.s)}]]){
                pq.push({1, eid[{min(a, e[pqi.s].s.s), max(a, e[pqi.s].s.s)}]});
            }
        }
    }

    FOR(i, 1, m) if(!v[i]){
        cout << 0 << endl;
        return 0;
    } 

    FOR(i, 1, m) cout << d[i] << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 231 ms 45000 KB Output is correct
5 Correct 2 ms 14680 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14848 KB Output is correct
13 Correct 200 ms 39128 KB Output is correct
14 Correct 262 ms 43456 KB Output is correct
15 Correct 232 ms 45256 KB Output is correct
16 Correct 183 ms 40652 KB Output is correct
17 Correct 232 ms 45000 KB Output is correct
18 Correct 273 ms 45188 KB Output is correct
19 Correct 215 ms 44372 KB Output is correct
20 Correct 2 ms 14680 KB Output is correct
21 Correct 3 ms 14936 KB Output is correct
22 Correct 240 ms 45132 KB Output is correct
23 Correct 188 ms 39108 KB Output is correct
24 Correct 237 ms 45080 KB Output is correct
25 Correct 192 ms 40364 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 14684 KB Output isn't correct
2 Incorrect 2 ms 14940 KB Output isn't correct
3 Correct 126 ms 42736 KB Output is correct
4 Correct 114 ms 43980 KB Output is correct
5 Correct 135 ms 43696 KB Output is correct
6 Runtime error 114 ms 97108 KB Execution killed with signal 11
7 Incorrect 2 ms 14684 KB Output isn't correct
8 Incorrect 2 ms 14684 KB Output isn't correct
9 Correct 2 ms 14808 KB Output is correct
10 Correct 2 ms 14800 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Incorrect 1 ms 14684 KB Output isn't correct
15 Incorrect 2 ms 14940 KB Output isn't correct
16 Incorrect 2 ms 14940 KB Output isn't correct
17 Correct 2 ms 14940 KB Output is correct
18 Correct 2 ms 15040 KB Output is correct
19 Correct 2 ms 14940 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 3 ms 15424 KB Output is correct
22 Incorrect 2 ms 14940 KB Output isn't correct
23 Incorrect 91 ms 38872 KB Output isn't correct
24 Incorrect 129 ms 44224 KB Output isn't correct
25 Correct 124 ms 42700 KB Output is correct
26 Correct 138 ms 44236 KB Output is correct
27 Correct 109 ms 43688 KB Output is correct
28 Runtime error 168 ms 89844 KB Execution killed with signal 11
29 Runtime error 129 ms 102480 KB Execution killed with signal 11
30 Incorrect 145 ms 43340 KB Output isn't correct
31 Incorrect 123 ms 44116 KB Output isn't correct
32 Incorrect 193 ms 44600 KB Output isn't correct
33 Correct 141 ms 44308 KB Output is correct
34 Correct 130 ms 43980 KB Output is correct
35 Correct 122 ms 43984 KB Output is correct
36 Runtime error 177 ms 87640 KB Execution killed with signal 11
37 Runtime error 141 ms 97544 KB Execution killed with signal 11
38 Incorrect 156 ms 44040 KB Output isn't correct
39 Incorrect 197 ms 44396 KB Output isn't correct
40 Incorrect 152 ms 44236 KB Output isn't correct
41 Correct 152 ms 44112 KB Output is correct
42 Correct 119 ms 43904 KB Output is correct
43 Correct 118 ms 43860 KB Output is correct
44 Correct 173 ms 43920 KB Output is correct
45 Runtime error 116 ms 89428 KB Execution killed with signal 11
46 Incorrect 143 ms 43924 KB Output isn't correct
47 Incorrect 129 ms 44232 KB Output isn't correct
48 Incorrect 117 ms 44100 KB Output isn't correct
49 Correct 135 ms 43092 KB Output is correct
50 Correct 116 ms 44236 KB Output is correct
51 Correct 146 ms 44432 KB Output is correct
52 Correct 110 ms 43728 KB Output is correct
53 Runtime error 114 ms 92220 KB Execution killed with signal 11
54 Incorrect 135 ms 43820 KB Output isn't correct