oj.uz

Submission #251582

# Submission time Handle Problem Language Result Execution time Memory
251582 2020-07-21T19:55:04 Z abacaba Pipes (BOI13_pipes) C++14
74.0741 / 100
 263 ms 66296 KB 
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

#define int long long

const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 5e5 + 15;
int n, m, a[N];
vector <int> g[N];
bool used[N];

set <pii> cur;
int deg[N], d[N];

int p[N], sz[N];
pii e[N];
int ans[N];

vector <int> comp[N];

set <int> cycles;
vector <int> inc;

int pref[2][N];

vector <int> G[N];

bool tw[N];
bool used2[N];

int find(int v) {
    if(v == p[v])
        return v;
    return p[v] = find(p[v]);
}

void unio(int a, int b) {
    a = find(a);
    b = find(b);
    if(a != b) {
        if(sz[a] < sz[b])
            swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
}

inline int gt(int i, int v) {
    return e[i].f == v ? e[i].se : e[i].f;
}

void precheck(int v, int p = -1) {
    used[v] = true;
    for(int ind : g[v]) {
        int to = gt(ind, v);
        if(to == p)
            continue;
        if(used[to]) {
            if(d[to] > d[v])
                continue;
            if((d[v] - d[to]) & 1) {
                cout << 0 << endl;
                exit(0);
            }
        }
        else {
            d[to] = d[v] + 1;
            precheck(to, v);
        }
    }
}

vector <int> now;

void dfs(int v) {
    used[v] = true;
    now.pb(v);
    for(int ind : g[v]) {
        int to = gt(ind, v);
        if(used[to] || find(v) != find(to))
            continue;
        dfs(to);
    }
}

inline int get(int k, int l, int r) {
    k = (k + 10) & 1;
    Max(l, 0LL);
    if(l > r)
        return 0;
    return pref[k][r] - (l == 0 ? 0 : pref[k][l-1]);
}

void solve_for_cycle(int s) {
    if(sz[s] == 1)
        return;
    now.clear();
    dfs(comp[s][0]);
    int sum = 0;
    for(int v : now)
        sum += a[v];
    for(int i = 0; i < now.size(); ++i) {
        for(int j = 0; j < 2; ++j)
            pref[j][i] = (i == 0 ? 0 : pref[j][i-1]);
        pref[i & 1][i] += a[now[i]];
    }
    for(int i = 0; i + 1 < now.size(); ++i) {
        int v = now[i];
        int ind = -1;
        for(int j = 0; j < g[v].size(); ++j)
            if(gt(g[v][j], v) == now[i + 1])
                ind = g[v][j];
        if(ind == -1)
            exit(0);
        int val = get(i + 2, i + 2, now.size() - 1) + get(i - 1, 0, i - 1);
        ans[ind] = sum - 2 * val;
    }
    int v = now.back();
    int ind = -1;
    for(int j = 0; j < g[v].size(); ++j)
        if(gt(g[v][j], v) == now[0])
            ind = g[v][j];
    int val = get(1, 1, now.size() - 2);
    ans[ind] = sum - 2 * val;
}

main() {
    for(int i = 0; i < N; ++i)
        p[i] = i, sz[i] = 1;
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    // setin("input.txt");
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= m; ++i) {
        cin >> e[i].f >> e[i].se;
        g[e[i].f].pb(i);
        g[e[i].se].pb(i);
    }
    precheck(1);
    for(int i = 1; i <= n; ++i)
        deg[i] = g[i].size(), cur.insert({g[i].size(), i});
    memset(used, 0, sizeof(used));
    while(!cur.empty()) {
        int v = cur.begin()->se;
        cur.erase(cur.begin());
        used[v] = true;
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(used[to] && deg[to] == 0)
                a[v] -= ans[ind] / 2;
        }
        if(deg[v] != 1)
            continue;
        deg[v] = 0;
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(used[to])
                continue;
            ans[ind] = 2 * a[v];
            cur.erase({deg[to], to});
            --deg[to];
            cur.insert({deg[to], to});
        }
    }
    for(int v = 1; v <= n; ++v) {
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(deg[v] > 1 && deg[to] > 1)
                unio(v, to);
        }
    }
    for(int v = 1; v <= n; ++v) {
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(find(v) != find(to) && deg[v] && deg[to]) {
                G[find(v)].pb(ind);
                G[find(to)].pb(ind);
            }
        }
    }
    memset(used, 0, sizeof(used));
    cur.clear();
    for(int i = 1; i <= n; ++i) {
        if(deg[i] != 0) {
            comp[find(i)].pb(i);
            deg[find(i)] = G[find(i)].size();
            cur.insert({deg[find(i)], find(i)});
        }
    }
    while(!cur.empty()) {
        int v = cur.begin()->se;
        cur.erase(cur.begin());

        used2[v] = true;
        for(int ind : G[v]) {
            int x = e[ind].f, y = e[ind].se;
            int to = (find(x) == v ? find(y) : find(x));
            if(used2[to])
                a[find(x) == v ? x : y] -= ans[ind] / 2;
        }
        solve_for_cycle(v);
        for(int ind : G[v]) {
            int x = e[ind].f, y = e[ind].se;
            int to = (find(x) == v ? find(y) : find(x));
            if(used2[to])
                continue;
            ans[ind] = 2 * a[find(x) == v ? x : y];
            cur.erase({deg[to], to});
            --deg[to];
            cur.insert({deg[to], to});
        }
    }
    for(int i = 1; i <= m; ++i)
        cout << ans[i] << endl;
    return 0;
}

Compilation message

pipes.cpp: In function 'void solve_for_cycle(long long int)':
pipes.cpp:160:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:165:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:168:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:178:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < g[v].size(); ++j)
                    ~~^~~~~~~~~~~~~
pipes.cpp: At global scope:
pipes.cpp:185:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43904 KB Output is correct
2 Correct 23 ms 43904 KB Output is correct
3 Correct 24 ms 44032 KB Output is correct
4 Correct 215 ms 59000 KB Output is correct
5 Correct 24 ms 43904 KB Output is correct
6 Correct 23 ms 43904 KB Output is correct
7 Correct 24 ms 43904 KB Output is correct
8 Correct 23 ms 43896 KB Output is correct
9 Correct 25 ms 44032 KB Output is correct
10 Correct 26 ms 44032 KB Output is correct
11 Correct 26 ms 44032 KB Output is correct
12 Correct 24 ms 44152 KB Output is correct
13 Correct 159 ms 55928 KB Output is correct
14 Correct 193 ms 58232 KB Output is correct
15 Correct 212 ms 59036 KB Output is correct
16 Correct 172 ms 56824 KB Output is correct
17 Correct 205 ms 59000 KB Output is correct
18 Correct 216 ms 59128 KB Output is correct
19 Correct 198 ms 61560 KB Output is correct
20 Correct 23 ms 43904 KB Output is correct
21 Correct 24 ms 44160 KB Output is correct
22 Correct 212 ms 59128 KB Output is correct
23 Correct 158 ms 55928 KB Output is correct
24 Correct 207 ms 59128 KB Output is correct
25 Correct 168 ms 56568 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43904 KB Output is correct
2 Correct 30 ms 44152 KB Output is correct
3 Correct 105 ms 52600 KB Output is correct
4 Incorrect 243 ms 62840 KB Output isn't correct
5 Incorrect 218 ms 58236 KB Output isn't correct
6 Correct 224 ms 66296 KB Output is correct
7 Correct 24 ms 43904 KB Output is correct
8 Correct 25 ms 43904 KB Output is correct
9 Correct 23 ms 43392 KB Output is correct
10 Incorrect 24 ms 43896 KB Output isn't correct
11 Incorrect 23 ms 43904 KB Output isn't correct
12 Incorrect 25 ms 43904 KB Output isn't correct
13 Correct 24 ms 43392 KB Output is correct
14 Correct 23 ms 43904 KB Output is correct
15 Correct 24 ms 44160 KB Output is correct
16 Correct 31 ms 44160 KB Output is correct
17 Correct 31 ms 43516 KB Output is correct
18 Incorrect 24 ms 44160 KB Output isn't correct
19 Incorrect 24 ms 44224 KB Output isn't correct
20 Incorrect 24 ms 44160 KB Output isn't correct
21 Correct 25 ms 43648 KB Output is correct
22 Correct 25 ms 44160 KB Output is correct
23 Correct 162 ms 58872 KB Output is correct
24 Correct 201 ms 61560 KB Output is correct
25 Correct 81 ms 52600 KB Output is correct
26 Incorrect 192 ms 62328 KB Output isn't correct
27 Incorrect 184 ms 62584 KB Output isn't correct
28 Incorrect 199 ms 58648 KB Output isn't correct
29 Correct 192 ms 61944 KB Output is correct
30 Correct 199 ms 63224 KB Output is correct
31 Correct 191 ms 63480 KB Output is correct
32 Correct 228 ms 59512 KB Output is correct
33 Correct 83 ms 53496 KB Output is correct
34 Incorrect 180 ms 61708 KB Output isn't correct
35 Incorrect 211 ms 62812 KB Output isn't correct
36 Incorrect 226 ms 58488 KB Output isn't correct
37 Correct 263 ms 66296 KB Output is correct
38 Correct 251 ms 62840 KB Output is correct
39 Correct 214 ms 59128 KB Output is correct
40 Correct 206 ms 61304 KB Output is correct
41 Correct 97 ms 55288 KB Output is correct
42 Incorrect 174 ms 61944 KB Output isn't correct
43 Incorrect 174 ms 63224 KB Output isn't correct
44 Incorrect 192 ms 58232 KB Output isn't correct
45 Correct 181 ms 63096 KB Output is correct
46 Correct 204 ms 63984 KB Output is correct
47 Correct 205 ms 61436 KB Output is correct
48 Correct 199 ms 63352 KB Output is correct
49 Correct 73 ms 50808 KB Output is correct
50 Incorrect 208 ms 61816 KB Output isn't correct
51 Incorrect 210 ms 60792 KB Output isn't correct
52 Incorrect 187 ms 59512 KB Output isn't correct
53 Correct 186 ms 63224 KB Output is correct
54 Correct 215 ms 62328 KB Output is correct