oj.uz

Submission #673501

# Submission time Handle Problem Language Result Execution time Memory
673501 2022-12-20T17:59:08 Z Lobo Pipes (BOI13_pipes) C++17
66.2963 / 100
 217 ms 72916 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 5e5+10;

int n, m, c[maxn], ans[maxn], gr[maxn];
vector<pair<int,int>> g[maxn], g1[maxn];
int sm = 0;
vector<int> vrt;
void dfs(int u, int ant, int cnt) {
    sm+= c[u]*cnt;
    auto V = g[u][0];
    if(V.fr == ant) V = g[u][1];
    int v = V.fr;
    if(v == vrt[0]) return;
    dfs(v,u,cnt*-1);
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for(int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(mp(v,i));
        g[v].pb(mp(u,i));
        gr[u]++;
        gr[v]++;
    }

    if(m > n) {
        cout << 0 << endl;
        return;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++) {
        if(gr[i] == 1) q.push(i);
    }

    while(q.size()) {
        int u = q.front(); q.pop();
        gr[u] = -1;
        for(auto V : g[u]) {
            int v = V.fr;
            int id = V.sc;
            if(gr[v] == -1) continue;
            ans[id] = 2*c[u];
            c[v]-= c[u];
            if(--gr[v] == 1) q.push(v);
        }
    }

    if(n == m) {
        for(int i = 1; i <= n; i++) {
            if(gr[i] != -1) {
                vrt.pb(i);
                for(auto V : g[i]) {
                    if(gr[V.fr] != -1) {
                        g1[i].pb(V);
                    }
                }
            }
        }

        if(vrt.size()%2 == 1) {
            dfs(vrt[0],-1,1);
            ans[g1[vrt[0]][1].sc] = sm;
            c[g1[vrt[0]][1].fr]-= sm/2;
            c[vrt[0]]-= sm/2;
            gr[g1[vrt[0]][1].fr]--;
            gr[vrt[0]]--;
            q.push(g1[vrt[0]][1].fr);
            q.push(vrt[0]);
        }
        else {
            assert(0);
        }

        while(q.size()) {
            int u = q.front(); q.pop();
            gr[u] = -1;
            for(auto V : g[u]) {
                int v = V.fr;
                int id = V.sc;
                if(gr[v] == -1 || id == g1[vrt[0]][1].sc) continue;
                ans[id] = 2*c[u];
                c[v]-= c[u];
                if(--gr[v] == 1) q.push(v);
            }
        }

    }



    for(int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 74 ms 32108 KB Output is correct
5 Correct 14 ms 23828 KB Output is correct
6 Correct 12 ms 23748 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 11 ms 23784 KB Output is correct
9 Correct 14 ms 23796 KB Output is correct
10 Correct 13 ms 23820 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 15 ms 23948 KB Output is correct
13 Correct 57 ms 30412 KB Output is correct
14 Correct 65 ms 31636 KB Output is correct
15 Correct 64 ms 32160 KB Output is correct
16 Correct 55 ms 30832 KB Output is correct
17 Correct 76 ms 32100 KB Output is correct
18 Correct 75 ms 32280 KB Output is correct
19 Correct 75 ms 31756 KB Output is correct
20 Correct 14 ms 23764 KB Output is correct
21 Correct 12 ms 23904 KB Output is correct
22 Correct 66 ms 32104 KB Output is correct
23 Correct 55 ms 30408 KB Output is correct
24 Correct 70 ms 32152 KB Output is correct
25 Correct 54 ms 30744 KB Output is correct

Subtask #2
36.2962962963 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 48096 KB Execution killed with signal 11
2 Runtime error 34 ms 48356 KB Execution killed with signal 11
3 Runtime error 90 ms 67384 KB Execution killed with signal 6
4 Correct 50 ms 30572 KB Output is correct
5 Correct 49 ms 30368 KB Output is correct
6 Correct 217 ms 51264 KB Output is correct
7 Runtime error 30 ms 48080 KB Execution killed with signal 11
8 Runtime error 33 ms 48112 KB Execution killed with signal 11
9 Runtime error 36 ms 48076 KB Execution killed with signal 6
10 Correct 12 ms 23728 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23800 KB Output is correct
14 Runtime error 31 ms 48032 KB Execution killed with signal 11
15 Runtime error 33 ms 48260 KB Execution killed with signal 11
16 Runtime error 31 ms 48304 KB Execution killed with signal 11
17 Runtime error 30 ms 48340 KB Execution killed with signal 6
18 Correct 14 ms 23888 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 12 ms 23864 KB Output is correct
21 Correct 12 ms 23864 KB Output is correct
22 Runtime error 29 ms 48312 KB Execution killed with signal 11
23 Runtime error 91 ms 66280 KB Execution killed with signal 11
24 Runtime error 100 ms 69128 KB Execution killed with signal 11
25 Runtime error 83 ms 67304 KB Execution killed with signal 6
26 Correct 48 ms 30540 KB Output is correct
27 Correct 51 ms 30412 KB Output is correct
28 Correct 54 ms 30872 KB Output is correct
29 Correct 172 ms 45928 KB Output is correct
30 Runtime error 88 ms 67732 KB Execution killed with signal 11
31 Runtime error 84 ms 72836 KB Execution killed with signal 11
32 Runtime error 86 ms 65176 KB Execution killed with signal 11
33 Runtime error 88 ms 69432 KB Execution killed with signal 6
34 Correct 58 ms 30448 KB Output is correct
35 Correct 55 ms 30512 KB Output is correct
36 Correct 50 ms 30612 KB Output is correct
37 Correct 179 ms 51244 KB Output is correct
38 Runtime error 98 ms 68536 KB Execution killed with signal 11
39 Runtime error 85 ms 64240 KB Execution killed with signal 11
40 Runtime error 84 ms 68712 KB Execution killed with signal 11
41 Runtime error 84 ms 72916 KB Execution killed with signal 6
42 Correct 49 ms 30408 KB Output is correct
43 Correct 51 ms 30404 KB Output is correct
44 Correct 52 ms 30360 KB Output is correct
45 Correct 140 ms 48492 KB Output is correct
46 Runtime error 83 ms 67460 KB Execution killed with signal 11
47 Correct 79 ms 34496 KB Output is correct
48 Runtime error 97 ms 72448 KB Execution killed with signal 11
49 Runtime error 94 ms 63976 KB Execution killed with signal 6
50 Correct 49 ms 30476 KB Output is correct
51 Correct 49 ms 30448 KB Output is correct
52 Correct 48 ms 30412 KB Output is correct
53 Correct 150 ms 47692 KB Output is correct
54 Runtime error 90 ms 67072 KB Execution killed with signal 11