oj.uz

Submission #673486

# Submission time Handle Problem Language Result Execution time Memory
673486 2022-12-20T17:10:45 Z Lobo Pipes (BOI13_pipes) C++17
65 / 100
 188 ms 52276 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+= cnt*c[u];
    auto V = g1[u][0];
    if(V.fr == ant) V = g1[u][1];
    int v = V.fr;
    int id = V.sc;
    if(v == vrt[0]) return;
    dfs(v,u,cnt*-1);
}

void dfs1(int u, int ant, int cnt) {
    auto V = g1[u][0];
    if(V.fr == ant) V = g1[u][1];
    int v = V.fr;
    int id = V.sc;
    ans[id] = cnt*sm;
    if(v == vrt[0]) return;
    dfs1(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(m == n) {
        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);
            dfs1(vrt[0],-1,1);
        }

    }

    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();
    }

}

Compilation message

pipes.cpp: In function 'void dfs(long long int, long long int, long long int)':
pipes.cpp:24:9: warning: unused variable 'id' [-Wunused-variable]
   24 |     int id = V.sc;
      |         ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 13 ms 23876 KB Output is correct
4 Correct 69 ms 32616 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 12 ms 23816 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 13 ms 23824 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 13 ms 23880 KB Output is correct
13 Correct 70 ms 30936 KB Output is correct
14 Correct 67 ms 32176 KB Output is correct
15 Correct 67 ms 32652 KB Output is correct
16 Correct 59 ms 31324 KB Output is correct
17 Correct 69 ms 32588 KB Output is correct
18 Correct 70 ms 32608 KB Output is correct
19 Correct 78 ms 32288 KB Output is correct
20 Correct 12 ms 23816 KB Output is correct
21 Correct 14 ms 23824 KB Output is correct
22 Correct 71 ms 32588 KB Output is correct
23 Correct 54 ms 30884 KB Output is correct
24 Correct 69 ms 32684 KB Output is correct
25 Correct 58 ms 31180 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23724 KB Output isn't correct
2 Incorrect 13 ms 23948 KB Output isn't correct
3 Incorrect 67 ms 34584 KB Output isn't correct
4 Correct 52 ms 31436 KB Output is correct
5 Correct 60 ms 31408 KB Output is correct
6 Correct 188 ms 52276 KB Output is correct
7 Incorrect 12 ms 23764 KB Output isn't correct
8 Incorrect 12 ms 23824 KB Output isn't correct
9 Incorrect 12 ms 23832 KB Output isn't correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23804 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Incorrect 12 ms 23764 KB Output isn't correct
15 Incorrect 13 ms 23892 KB Output isn't correct
16 Incorrect 13 ms 23824 KB Output isn't correct
17 Incorrect 13 ms 23888 KB Output isn't correct
18 Correct 12 ms 23820 KB Output is correct
19 Correct 13 ms 23836 KB Output is correct
20 Correct 13 ms 23892 KB Output is correct
21 Correct 13 ms 24020 KB Output is correct
22 Incorrect 13 ms 23840 KB Output isn't correct
23 Incorrect 63 ms 33988 KB Output isn't correct
24 Incorrect 86 ms 35552 KB Output isn't correct
25 Incorrect 73 ms 34500 KB Output isn't correct
26 Correct 53 ms 31540 KB Output is correct
27 Correct 55 ms 31356 KB Output is correct
28 Correct 53 ms 31756 KB Output is correct
29 Correct 150 ms 46964 KB Output is correct
30 Incorrect 88 ms 34924 KB Output isn't correct
31 Incorrect 90 ms 37460 KB Output isn't correct
32 Incorrect 72 ms 33536 KB Output isn't correct
33 Incorrect 72 ms 35640 KB Output isn't correct
34 Correct 53 ms 31444 KB Output is correct
35 Correct 52 ms 31508 KB Output is correct
36 Correct 55 ms 31560 KB Output is correct
37 Correct 183 ms 52272 KB Output is correct
38 Incorrect 79 ms 35268 KB Output isn't correct
39 Incorrect 68 ms 33196 KB Output isn't correct
40 Incorrect 82 ms 35324 KB Output isn't correct
41 Incorrect 70 ms 37200 KB Output isn't correct
42 Correct 51 ms 31440 KB Output is correct
43 Correct 51 ms 31424 KB Output is correct
44 Correct 49 ms 31272 KB Output is correct
45 Correct 151 ms 49220 KB Output is correct
46 Incorrect 77 ms 34792 KB Output isn't correct
47 Incorrect 83 ms 35544 KB Output isn't correct
48 Incorrect 87 ms 37252 KB Output isn't correct
49 Incorrect 66 ms 32912 KB Output isn't correct
50 Correct 51 ms 31660 KB Output is correct
51 Correct 53 ms 31432 KB Output is correct
52 Correct 52 ms 31320 KB Output is correct
53 Correct 149 ms 48636 KB Output is correct
54 Incorrect 83 ms 34500 KB Output isn't correct