oj.uz

Submission #673503

# Submission time Handle Problem Language Result Execution time Memory
673503 2022-12-20T18:01:00 Z Lobo Pipes (BOI13_pipes) C++17
90.9259 / 100
 179 ms 72868 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 = g1[u][0];
    if(V.fr == ant) V = g1[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 23836 KB Output is correct
2 Correct 12 ms 23760 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 65 ms 32076 KB Output is correct
5 Correct 12 ms 23716 KB Output is correct
6 Correct 12 ms 23716 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 15 ms 23812 KB Output is correct
10 Correct 12 ms 23852 KB Output is correct
11 Correct 14 ms 23892 KB Output is correct
12 Correct 14 ms 23892 KB Output is correct
13 Correct 57 ms 30356 KB Output is correct
14 Correct 64 ms 31564 KB Output is correct
15 Correct 70 ms 32088 KB Output is correct
16 Correct 65 ms 30864 KB Output is correct
17 Correct 80 ms 32056 KB Output is correct
18 Correct 70 ms 32176 KB Output is correct
19 Correct 79 ms 31676 KB Output is correct
20 Correct 13 ms 23764 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Correct 81 ms 32100 KB Output is correct
23 Correct 58 ms 30412 KB Output is correct
24 Correct 67 ms 32132 KB Output is correct
25 Correct 55 ms 30672 KB Output is correct

Subtask #2
60.9259259259 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Runtime error 124 ms 67348 KB Execution killed with signal 6
4 Correct 52 ms 30504 KB Output is correct
5 Correct 51 ms 30220 KB Output is correct
6 Correct 179 ms 51388 KB Output is correct
7 Correct 15 ms 23828 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Runtime error 31 ms 48092 KB Execution killed with signal 6
10 Correct 12 ms 23764 KB Output is correct
11 Correct 14 ms 23784 KB Output is correct
12 Correct 12 ms 23784 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 15 ms 23836 KB Output is correct
15 Correct 13 ms 23968 KB Output is correct
16 Correct 13 ms 23892 KB Output is correct
17 Runtime error 32 ms 48252 KB Execution killed with signal 6
18 Correct 13 ms 23760 KB Output is correct
19 Correct 12 ms 23796 KB Output is correct
20 Correct 13 ms 23808 KB Output is correct
21 Correct 14 ms 23892 KB Output is correct
22 Correct 12 ms 23892 KB Output is correct
23 Correct 71 ms 33048 KB Output is correct
24 Correct 89 ms 34564 KB Output is correct
25 Runtime error 94 ms 67404 KB Execution killed with signal 6
26 Correct 54 ms 30580 KB Output is correct
27 Correct 48 ms 30436 KB Output is correct
28 Correct 59 ms 30828 KB Output is correct
29 Correct 162 ms 45984 KB Output is correct
30 Correct 82 ms 33936 KB Output is correct
31 Correct 100 ms 36448 KB Output is correct
32 Correct 77 ms 32588 KB Output is correct
33 Runtime error 94 ms 69484 KB Execution killed with signal 6
34 Correct 52 ms 30524 KB Output is correct
35 Correct 65 ms 30572 KB Output is correct
36 Correct 52 ms 30540 KB Output is correct
37 Correct 170 ms 51316 KB Output is correct
38 Correct 84 ms 34204 KB Output is correct
39 Correct 71 ms 32220 KB Output is correct
40 Correct 99 ms 34396 KB Output is correct
41 Runtime error 91 ms 72868 KB Execution killed with signal 6
42 Correct 54 ms 30468 KB Output is correct
43 Correct 66 ms 30468 KB Output is correct
44 Correct 50 ms 30260 KB Output is correct
45 Correct 174 ms 48348 KB Output is correct
46 Correct 83 ms 33756 KB Output is correct
47 Correct 87 ms 34444 KB Output is correct
48 Correct 88 ms 36320 KB Output is correct
49 Runtime error 78 ms 64028 KB Execution killed with signal 6
50 Correct 54 ms 30536 KB Output is correct
51 Correct 57 ms 30460 KB Output is correct
52 Correct 53 ms 30428 KB Output is correct
53 Correct 141 ms 47624 KB Output is correct
54 Correct 78 ms 33632 KB Output is correct