oj.uz

답안 #251620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251620 2020-07-22T03:47:45 Z abacaba Pipes (BOI13_pipes) C++14
44.0741 / 100
 223 ms 66556 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 pp[N];
int ans[N];
 
int pref[2][N];

int cnt;

vector <int> now;

bool cycle[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) {
    used[v] = true;
    for(int ind : g[v]) {
        int to = gt(ind, v);
        if(to == pp[v])
            continue;
        if(used[to]) {
            if(d[to] > d[v])
                continue;
            if((d[v] - d[to]) & 1) {
                cout << 0 << endl;
                exit(0);
            }
            ++cnt;
            if(cnt > 1) {
                cout << 0 << endl;
                exit(0);
            }
            int u = v;
            while(u != to) {
                unio(u, pp[u]);
                u = pp[u];
            }
            u = v;
            while(u != pp[to]) {
                cycle[u] = true;
                now.pb(u);
                u = pp[u];
            }
        }
        else {
            d[to] = d[v] + 1;
            pp[to] = v;
            precheck(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];
        // if(ind == -1) {
        //     cout << "ASdasd" << endl;
        //     exit(0);
        // }
        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];
    // if(ind == -1) {
    //     cout << "ASdasd" << endl;
    //     exit(0);
    // }
    assert(ind != -1);
    int val = get(1, 1, now.size() - 2);
    ans[ind] = sum - 2 * val;
}

int q[N], ql, qr;

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);
    memset(used, 0, sizeof(used));
    ql = 0, qr = -1;
    for(int i = 1; i <= n; ++i) {
        deg[i] = g[i].size();
        if(deg[i] == 1) {
            q[++qr] = i;
            used[i] = true;
        }
    }
    while(ql <= qr) {
        int v = q[ql++];
        if(cycle[v])
            break;
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(used[to] && deg[to] == 1)
                a[v] -= ans[ind] / 2;
        }
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(used[to])
                continue;
            ans[ind] = 2 * a[v];
            --deg[to];
            if(deg[to] == 1) {
                q[++qr] = to;
                used[to] = true;
            }
        }
    }
    memset(used, 0, sizeof(used));
    solve_for_cycle();
    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:158:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:163:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:166:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:179: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:193:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 41208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 35 ms 41208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 39 ms 41464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 123 ms 61560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 35 ms 41208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 35 ms 41208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 35 ms 41336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 37 ms 41208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 37 ms 41464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 42 ms 41464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 35 ms 41464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 40 ms 41464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 132 ms 57340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 123 ms 60280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 129 ms 61432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 116 ms 58360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 121 ms 61432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 121 ms 61432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 135 ms 66556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 34 ms 41208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 42 ms 41464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 123 ms 61432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 104 ms 57336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 155 ms 61688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 112 ms 58232 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 20480 KB Output isn't correct
2 Incorrect 14 ms 20608 KB Output isn't correct
3 Correct 72 ms 29944 KB Output is correct
4 Correct 81 ms 32760 KB Output is correct
5 Correct 67 ms 27512 KB Output is correct
6 Correct 217 ms 43000 KB Output is correct
7 Incorrect 11 ms 20480 KB Output isn't correct
8 Incorrect 14 ms 20480 KB Output isn't correct
9 Correct 15 ms 19968 KB Output is correct
10 Correct 12 ms 19968 KB Output is correct
11 Correct 12 ms 19968 KB Output is correct
12 Correct 12 ms 19968 KB Output is correct
13 Correct 13 ms 19968 KB Output is correct
14 Incorrect 11 ms 20480 KB Output isn't correct
15 Incorrect 12 ms 20608 KB Output isn't correct
16 Incorrect 12 ms 20608 KB Output isn't correct
17 Correct 13 ms 20096 KB Output is correct
18 Correct 11 ms 20096 KB Output is correct
19 Correct 11 ms 20096 KB Output is correct
20 Correct 11 ms 20096 KB Output is correct
21 Correct 11 ms 20096 KB Output is correct
22 Incorrect 11 ms 20608 KB Output isn't correct
23 Incorrect 88 ms 33004 KB Output isn't correct
24 Incorrect 109 ms 35056 KB Output isn't correct
25 Correct 69 ms 29820 KB Output is correct
26 Correct 80 ms 31864 KB Output is correct
27 Correct 82 ms 31992 KB Output is correct
28 Correct 62 ms 26608 KB Output is correct
29 Correct 180 ms 38520 KB Output is correct
30 Incorrect 124 ms 36596 KB Output isn't correct
31 Incorrect 113 ms 37608 KB Output isn't correct
32 Incorrect 103 ms 32504 KB Output isn't correct
33 Correct 73 ms 30840 KB Output is correct
34 Correct 80 ms 31176 KB Output is correct
35 Correct 84 ms 32888 KB Output is correct
36 Correct 59 ms 27512 KB Output is correct
37 Correct 222 ms 43000 KB Output is correct
38 Incorrect 110 ms 36076 KB Output isn't correct
39 Incorrect 102 ms 32032 KB Output isn't correct
40 Incorrect 111 ms 34672 KB Output isn't correct
41 Correct 81 ms 32632 KB Output is correct
42 Correct 110 ms 31604 KB Output is correct
43 Correct 89 ms 33016 KB Output is correct
44 Correct 75 ms 27512 KB Output is correct
45 Correct 223 ms 39672 KB Output is correct
46 Incorrect 151 ms 37236 KB Output isn't correct
47 Incorrect 137 ms 34932 KB Output isn't correct
48 Incorrect 141 ms 37352 KB Output isn't correct
49 Correct 63 ms 28024 KB Output is correct
50 Correct 79 ms 31352 KB Output is correct
51 Correct 82 ms 29816 KB Output is correct
52 Correct 78 ms 28280 KB Output is correct
53 Correct 216 ms 39800 KB Output is correct
54 Incorrect 111 ms 35436 KB Output isn't correct