oj.uz

Submission #673500

# Submission time Handle Problem Language Result Execution time Memory
673500 2022-12-20T17:58:28 Z Lobo Pipes (BOI13_pipes) C++17
66.2963 / 100
 185 ms 72788 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]);
        }

        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 12 ms 23764 KB Output is correct
2 Correct 12 ms 23792 KB Output is correct
3 Correct 15 ms 23844 KB Output is correct
4 Correct 73 ms 32056 KB Output is correct
5 Correct 12 ms 23832 KB Output is correct
6 Correct 13 ms 23824 KB Output is correct
7 Correct 13 ms 23800 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 11 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 11 ms 23892 KB Output is correct
12 Correct 12 ms 23908 KB Output is correct
13 Correct 51 ms 30328 KB Output is correct
14 Correct 67 ms 31564 KB Output is correct
15 Correct 86 ms 32100 KB Output is correct
16 Correct 58 ms 30836 KB Output is correct
17 Correct 67 ms 32072 KB Output is correct
18 Correct 78 ms 32152 KB Output is correct
19 Correct 77 ms 31736 KB Output is correct
20 Correct 13 ms 23764 KB Output is correct
21 Correct 14 ms 23812 KB Output is correct
22 Correct 68 ms 32120 KB Output is correct
23 Correct 51 ms 30420 KB Output is correct
24 Correct 67 ms 32100 KB Output is correct
25 Correct 61 ms 30712 KB Output is correct

Subtask #2
36.2962962963 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 48076 KB Execution killed with signal 11
2 Runtime error 32 ms 48332 KB Execution killed with signal 11
3 Incorrect 74 ms 33600 KB Output isn't correct
4 Correct 49 ms 30476 KB Output is correct
5 Correct 53 ms 30268 KB Output is correct
6 Correct 182 ms 51296 KB Output is correct
7 Runtime error 36 ms 48064 KB Execution killed with signal 11
8 Runtime error 32 ms 48112 KB Execution killed with signal 11
9 Incorrect 12 ms 23764 KB Output isn't correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 15 ms 23764 KB Output is correct
14 Runtime error 38 ms 48072 KB Execution killed with signal 11
15 Runtime error 32 ms 48332 KB Execution killed with signal 11
16 Runtime error 33 ms 48200 KB Execution killed with signal 11
17 Incorrect 13 ms 23892 KB Output isn't correct
18 Correct 12 ms 23764 KB Output is correct
19 Correct 14 ms 23836 KB Output is correct
20 Correct 12 ms 23892 KB Output is correct
21 Correct 13 ms 23984 KB Output is correct
22 Runtime error 30 ms 48280 KB Execution killed with signal 11
23 Runtime error 75 ms 66228 KB Execution killed with signal 11
24 Runtime error 95 ms 69244 KB Execution killed with signal 11
25 Incorrect 64 ms 33592 KB Output isn't correct
26 Correct 49 ms 30584 KB Output is correct
27 Correct 48 ms 30368 KB Output is correct
28 Correct 64 ms 30744 KB Output is correct
29 Correct 155 ms 45920 KB Output is correct
30 Runtime error 86 ms 67748 KB Execution killed with signal 11
31 Runtime error 90 ms 72788 KB Execution killed with signal 11
32 Runtime error 87 ms 65028 KB Execution killed with signal 11
33 Incorrect 68 ms 34588 KB Output isn't correct
34 Correct 48 ms 30552 KB Output is correct
35 Correct 51 ms 30576 KB Output is correct
36 Correct 54 ms 30568 KB Output is correct
37 Correct 185 ms 51312 KB Output is correct
38 Runtime error 96 ms 68400 KB Execution killed with signal 11
39 Runtime error 93 ms 64232 KB Execution killed with signal 11
40 Runtime error 97 ms 68660 KB Execution killed with signal 11
41 Incorrect 72 ms 36248 KB Output isn't correct
42 Correct 58 ms 30472 KB Output is correct
43 Correct 52 ms 30452 KB Output is correct
44 Correct 55 ms 30316 KB Output is correct
45 Correct 140 ms 48204 KB Output is correct
46 Runtime error 86 ms 67520 KB Execution killed with signal 11
47 Correct 88 ms 34500 KB Output is correct
48 Runtime error 85 ms 72508 KB Execution killed with signal 11
49 Incorrect 66 ms 31920 KB Output isn't correct
50 Correct 62 ms 30540 KB Output is correct
51 Correct 56 ms 30464 KB Output is correct
52 Correct 49 ms 30448 KB Output is correct
53 Correct 165 ms 47676 KB Output is correct
54 Runtime error 96 ms 67148 KB Execution killed with signal 11