oj.uz

Submission #251571

# Submission time Handle Problem Language Result Execution time Memory
251571 2020-07-21T19:40:57 Z abacaba Pipes (BOI13_pipes) C++14
74.0741 / 100
 340 ms 129912 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];
        assert(ind != -1);
        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] != 0 && deg[to] != 0) {
                G[find(v)].pb(ind);
                G[find(to)].pb(ind);
            }
        }
    }
    memset(used, 0, sizeof(used));
    cur.clear();
    for(int i = 1; i <= n; ++i) {
        comp[find(i)].pb(i);
        tw[find(i)] = true;
        deg[find(i)] = G[find(i)].size();
        cur.insert({deg[find(i)], find(i)});
    }

    memset(used, 0, sizeof(used));
    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:177: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:184: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 33 ms 43904 KB Output is correct
2 Correct 23 ms 43896 KB Output is correct
3 Correct 26 ms 44160 KB Output is correct
4 Correct 267 ms 62332 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 24 ms 43904 KB Output is correct
9 Correct 24 ms 44288 KB Output is correct
10 Correct 25 ms 44152 KB Output is correct
11 Correct 28 ms 44152 KB Output is correct
12 Correct 26 ms 44160 KB Output is correct
13 Correct 192 ms 58616 KB Output is correct
14 Correct 268 ms 61304 KB Output is correct
15 Correct 248 ms 62456 KB Output is correct
16 Correct 214 ms 59640 KB Output is correct
17 Correct 264 ms 62328 KB Output is correct
18 Correct 253 ms 62480 KB Output is correct
19 Correct 266 ms 65016 KB Output is correct
20 Correct 27 ms 43896 KB Output is correct
21 Correct 26 ms 44160 KB Output is correct
22 Correct 263 ms 62456 KB Output is correct
23 Correct 207 ms 58616 KB Output is correct
24 Correct 277 ms 62464 KB Output is correct
25 Correct 217 ms 59384 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 24 ms 44160 KB Output is correct
3 Correct 89 ms 52568 KB Output is correct
4 Runtime error 298 ms 129912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 315 ms 120948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 282 ms 66296 KB Output is correct
7 Correct 24 ms 43904 KB Output is correct
8 Correct 31 ms 43904 KB Output is correct
9 Correct 27 ms 43384 KB Output is correct
10 Runtime error 71 ms 88824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 70 ms 88824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 74 ms 88820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 23 ms 43392 KB Output is correct
14 Correct 26 ms 43896 KB Output is correct
15 Correct 43 ms 44152 KB Output is correct
16 Correct 24 ms 44160 KB Output is correct
17 Correct 23 ms 43520 KB Output is correct
18 Runtime error 76 ms 89208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 96 ms 89208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 77 ms 89208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Correct 30 ms 43648 KB Output is correct
22 Correct 30 ms 44160 KB Output is correct
23 Correct 187 ms 60164 KB Output is correct
24 Correct 241 ms 63096 KB Output is correct
25 Correct 116 ms 52600 KB Output is correct
26 Runtime error 285 ms 128480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 262 ms 123036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 302 ms 121080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Correct 226 ms 61944 KB Output is correct
30 Correct 234 ms 65016 KB Output is correct
31 Correct 212 ms 65528 KB Output is correct
32 Correct 258 ms 62488 KB Output is correct
33 Correct 90 ms 53496 KB Output is correct
34 Runtime error 270 ms 127608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 313 ms 129912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 340 ms 120612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Correct 299 ms 66276 KB Output is correct
38 Correct 269 ms 64632 KB Output is correct
39 Correct 256 ms 62328 KB Output is correct
40 Correct 236 ms 63224 KB Output is correct
41 Correct 89 ms 55288 KB Output is correct
42 Runtime error 230 ms 128632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 235 ms 124416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 270 ms 120948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Correct 176 ms 63348 KB Output is correct
46 Correct 230 ms 65776 KB Output is correct
47 Correct 218 ms 63228 KB Output is correct
48 Correct 203 ms 65400 KB Output is correct
49 Correct 87 ms 50808 KB Output is correct
50 Runtime error 268 ms 127288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 290 ms 124536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 264 ms 124280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Correct 199 ms 63224 KB Output is correct
54 Correct 230 ms 63988 KB Output is correct