oj.uz

Submission #251559

# Submission time Handle Problem Language Result Execution time Memory
251559 2020-07-21T19:29:36 Z abacaba Pipes (BOI13_pipes) C++14
74.0741 / 100
 245 ms 72436 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];

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

int pref[2][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 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] == 1)
                a[v] -= ans[ind] / 2;
        }
        if(deg[v] != 1)
            continue;
        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);
        }
    }
    int cnt = 0;
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; ++i) {
        if(sz[find(i)] > 1 && !used[i]) {
            dfs(i);
            solve_for_cycle();
            ++cnt;
        }
    }
    assert(cnt <= 1);
    for(int i = 1; i <= m; ++i)
        cout << ans[i] << endl;
    return 0;
}

Compilation message

pipes.cpp: In function 'void solve_for_cycle()':
pipes.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:154:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:157:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:166: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:173: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 11 ms 20480 KB Output is correct
2 Correct 15 ms 20608 KB Output is correct
3 Correct 12 ms 20608 KB Output is correct
4 Correct 194 ms 35576 KB Output is correct
5 Correct 11 ms 20480 KB Output is correct
6 Correct 11 ms 20480 KB Output is correct
7 Correct 11 ms 20480 KB Output is correct
8 Correct 11 ms 20480 KB Output is correct
9 Correct 12 ms 20608 KB Output is correct
10 Correct 12 ms 20608 KB Output is correct
11 Correct 12 ms 20608 KB Output is correct
12 Correct 12 ms 20608 KB Output is correct
13 Correct 149 ms 32548 KB Output is correct
14 Correct 178 ms 34680 KB Output is correct
15 Correct 192 ms 35576 KB Output is correct
16 Correct 166 ms 33400 KB Output is correct
17 Correct 210 ms 35572 KB Output is correct
18 Correct 191 ms 35576 KB Output is correct
19 Correct 226 ms 38124 KB Output is correct
20 Correct 12 ms 20480 KB Output is correct
21 Correct 13 ms 20608 KB Output is correct
22 Correct 224 ms 35576 KB Output is correct
23 Correct 152 ms 32376 KB Output is correct
24 Correct 197 ms 35576 KB Output is correct
25 Correct 155 ms 33028 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20480 KB Output is correct
2 Correct 13 ms 20608 KB Output is correct
3 Correct 68 ms 29048 KB Output is correct
4 Runtime error 201 ms 70904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 210 ms 59428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 226 ms 42872 KB Output is correct
7 Correct 11 ms 20480 KB Output is correct
8 Correct 11 ms 20480 KB Output is correct
9 Correct 11 ms 19968 KB Output is correct
10 Runtime error 35 ms 41216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 34 ms 41204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 34 ms 41216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 11 ms 19968 KB Output is correct
14 Correct 11 ms 20480 KB Output is correct
15 Correct 12 ms 20608 KB Output is correct
16 Correct 12 ms 20608 KB Output is correct
17 Correct 11 ms 20096 KB Output is correct
18 Runtime error 35 ms 41600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 36 ms 41592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 43 ms 41592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Correct 16 ms 20096 KB Output is correct
22 Correct 13 ms 20608 KB Output is correct
23 Correct 142 ms 35320 KB Output is correct
24 Correct 221 ms 38136 KB Output is correct
25 Correct 71 ms 29048 KB Output is correct
26 Runtime error 208 ms 69524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 189 ms 70956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 229 ms 60944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Correct 181 ms 38392 KB Output is correct
30 Correct 195 ms 39804 KB Output is correct
31 Correct 209 ms 40060 KB Output is correct
32 Correct 229 ms 36092 KB Output is correct
33 Correct 79 ms 29944 KB Output is correct
34 Runtime error 245 ms 68852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 218 ms 70916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 207 ms 60152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Correct 227 ms 42744 KB Output is correct
38 Correct 191 ms 39288 KB Output is correct
39 Correct 196 ms 35576 KB Output is correct
40 Correct 188 ms 37880 KB Output is correct
41 Correct 82 ms 31868 KB Output is correct
42 Runtime error 189 ms 70104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 186 ms 72436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 218 ms 59428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Correct 173 ms 39672 KB Output is correct
46 Correct 183 ms 40568 KB Output is correct
47 Correct 191 ms 37880 KB Output is correct
48 Correct 175 ms 39808 KB Output is correct
49 Correct 62 ms 27384 KB Output is correct
50 Runtime error 206 ms 67968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 215 ms 64476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 193 ms 64224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Correct 179 ms 39672 KB Output is correct
54 Correct 196 ms 38776 KB Output is correct