oj.uz

답안 #251577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251577 2020-07-21T19:44:53 Z abacaba Pipes (BOI13_pipes) C++14
74.0741 / 100
 341 ms 120052 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) {
        if(deg[find(i)] != 0) {
            comp[find(i)].pb(i);
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 43904 KB Output is correct
2 Correct 23 ms 43904 KB Output is correct
3 Correct 31 ms 44024 KB Output is correct
4 Correct 199 ms 58984 KB Output is correct
5 Correct 25 ms 43944 KB Output is correct
6 Correct 29 ms 43904 KB Output is correct
7 Correct 22 ms 43904 KB Output is correct
8 Correct 25 ms 43904 KB Output is correct
9 Correct 24 ms 44032 KB Output is correct
10 Correct 23 ms 44032 KB Output is correct
11 Correct 26 ms 44032 KB Output is correct
12 Correct 24 ms 44164 KB Output is correct
13 Correct 163 ms 55928 KB Output is correct
14 Correct 191 ms 58232 KB Output is correct
15 Correct 206 ms 59128 KB Output is correct
16 Correct 175 ms 56824 KB Output is correct
17 Correct 205 ms 59000 KB Output is correct
18 Correct 207 ms 59128 KB Output is correct
19 Correct 201 ms 61560 KB Output is correct
20 Correct 25 ms 43904 KB Output is correct
21 Correct 31 ms 44032 KB Output is correct
22 Correct 259 ms 59128 KB Output is correct
23 Correct 205 ms 55928 KB Output is correct
24 Correct 212 ms 59128 KB Output is correct
25 Correct 170 ms 56568 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 43904 KB Output is correct
2 Correct 24 ms 44160 KB Output is correct
3 Correct 89 ms 52576 KB Output is correct
4 Runtime error 265 ms 118424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 258 ms 106920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 289 ms 66296 KB Output is correct
7 Correct 28 ms 43904 KB Output is correct
8 Correct 24 ms 43904 KB Output is correct
9 Correct 28 ms 43392 KB Output is correct
10 Runtime error 70 ms 88812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 71 ms 88824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 74 ms 88824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 23 ms 43392 KB Output is correct
14 Correct 28 ms 43904 KB Output is correct
15 Correct 25 ms 44160 KB Output is correct
16 Correct 25 ms 44160 KB Output is correct
17 Correct 25 ms 43520 KB Output is correct
18 Runtime error 74 ms 89208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 69 ms 89208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 69 ms 89080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Correct 24 ms 43648 KB Output is correct
22 Correct 25 ms 44160 KB Output is correct
23 Correct 177 ms 58848 KB Output is correct
24 Correct 203 ms 61560 KB Output is correct
25 Correct 79 ms 52600 KB Output is correct
26 Runtime error 240 ms 116980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 307 ms 118572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 333 ms 108408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Correct 258 ms 61944 KB Output is correct
30 Correct 195 ms 63412 KB Output is correct
31 Correct 267 ms 63480 KB Output is correct
32 Correct 291 ms 59512 KB Output is correct
33 Correct 112 ms 53496 KB Output is correct
34 Runtime error 234 ms 116216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 325 ms 118396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 341 ms 107640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Correct 293 ms 66296 KB Output is correct
38 Correct 274 ms 62712 KB Output is correct
39 Correct 224 ms 59148 KB Output is correct
40 Correct 268 ms 61304 KB Output is correct
41 Correct 113 ms 55288 KB Output is correct
42 Runtime error 241 ms 117776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 311 ms 120052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 296 ms 106916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Correct 200 ms 63240 KB Output is correct
46 Correct 261 ms 63992 KB Output is correct
47 Correct 278 ms 61432 KB Output is correct
48 Correct 193 ms 63412 KB Output is correct
49 Correct 76 ms 50808 KB Output is correct
50 Runtime error 247 ms 115584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 258 ms 112168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 230 ms 111848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Correct 198 ms 63224 KB Output is correct
54 Correct 215 ms 62240 KB Output is correct