oj.uz

Submission #673502

# Submission time Handle Problem Language Result Execution time Memory
673502 2022-12-20T18:00:04 Z Lobo Pipes (BOI13_pipes) C++17
65 / 100
 190 ms 72928 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);
        }
        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 12 ms 23764 KB Output is correct
2 Correct 11 ms 23732 KB Output is correct
3 Correct 12 ms 23916 KB Output is correct
4 Correct 66 ms 32052 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 13 ms 23876 KB Output is correct
10 Correct 12 ms 23912 KB Output is correct
11 Correct 12 ms 23844 KB Output is correct
12 Correct 12 ms 23800 KB Output is correct
13 Correct 54 ms 30360 KB Output is correct
14 Correct 60 ms 31672 KB Output is correct
15 Correct 65 ms 32064 KB Output is correct
16 Correct 57 ms 30920 KB Output is correct
17 Correct 64 ms 32012 KB Output is correct
18 Correct 70 ms 32128 KB Output is correct
19 Correct 85 ms 31692 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23804 KB Output is correct
22 Correct 68 ms 32128 KB Output is correct
23 Correct 69 ms 30296 KB Output is correct
24 Correct 70 ms 32132 KB Output is correct
25 Correct 55 ms 30640 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48016 KB Execution killed with signal 11
2 Runtime error 31 ms 48240 KB Execution killed with signal 11
3 Runtime error 79 ms 67296 KB Execution killed with signal 6
4 Correct 52 ms 30492 KB Output is correct
5 Correct 48 ms 30280 KB Output is correct
6 Correct 179 ms 51264 KB Output is correct
7 Runtime error 30 ms 48020 KB Execution killed with signal 11
8 Runtime error 30 ms 48064 KB Execution killed with signal 11
9 Runtime error 31 ms 48084 KB Execution killed with signal 6
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Runtime error 30 ms 48004 KB Execution killed with signal 11
15 Runtime error 35 ms 48336 KB Execution killed with signal 11
16 Runtime error 30 ms 48220 KB Execution killed with signal 11
17 Runtime error 29 ms 48324 KB Execution killed with signal 6
18 Correct 12 ms 23828 KB Output is correct
19 Correct 12 ms 23892 KB Output is correct
20 Correct 12 ms 23896 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Runtime error 28 ms 48196 KB Execution killed with signal 11
23 Runtime error 75 ms 66280 KB Execution killed with signal 11
24 Runtime error 84 ms 69208 KB Execution killed with signal 11
25 Runtime error 85 ms 67524 KB Execution killed with signal 6
26 Correct 50 ms 30504 KB Output is correct
27 Correct 48 ms 30420 KB Output is correct
28 Correct 59 ms 30728 KB Output is correct
29 Correct 147 ms 45948 KB Output is correct
30 Runtime error 96 ms 67748 KB Execution killed with signal 11
31 Runtime error 87 ms 72792 KB Execution killed with signal 11
32 Runtime error 80 ms 65136 KB Execution killed with signal 11
33 Runtime error 89 ms 69428 KB Execution killed with signal 6
34 Correct 53 ms 30524 KB Output is correct
35 Correct 49 ms 30580 KB Output is correct
36 Correct 49 ms 30524 KB Output is correct
37 Correct 190 ms 51336 KB Output is correct
38 Runtime error 83 ms 68412 KB Execution killed with signal 11
39 Runtime error 88 ms 64332 KB Execution killed with signal 11
40 Runtime error 89 ms 68688 KB Execution killed with signal 11
41 Runtime error 86 ms 72928 KB Execution killed with signal 6
42 Correct 49 ms 30412 KB Output is correct
43 Correct 48 ms 30396 KB Output is correct
44 Correct 50 ms 30284 KB Output is correct
45 Correct 164 ms 48344 KB Output is correct
46 Runtime error 83 ms 67520 KB Execution killed with signal 11
47 Runtime error 89 ms 68948 KB Execution killed with signal 6
48 Runtime error 87 ms 72476 KB Execution killed with signal 11
49 Runtime error 76 ms 63964 KB Execution killed with signal 6
50 Correct 49 ms 30468 KB Output is correct
51 Correct 51 ms 30504 KB Output is correct
52 Correct 49 ms 30428 KB Output is correct
53 Correct 150 ms 47692 KB Output is correct
54 Runtime error 96 ms 67076 KB Execution killed with signal 11