oj.uz

답안 #251614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251614 2020-07-22T03:31:18 Z abacaba Pipes (BOI13_pipes) C++14
65 / 100
 340 ms 43128 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];
 
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) {
    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);
            }
            int u = v;
            while(u != to) {
                unio(u, pp[u]);
                u = pp[u];
            }
        }
        else {
            d[to] = d[v] + 1;
            pp[to] = v;
            precheck(to);
        }
    }
}

vector <int> now;

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;
}
 
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});
        }
    }
    set <int> is = {};
    for(int i = 1; i <= n; ++i)
        if(sz[find(i)] > 1)
            is.insert(find(i));
    if(is.size() > 1)
        return cout << 0 << endl, 0;
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; ++i) {
        if(sz[find(i)] > 1 && !used[i]) {
            now.clear();
            int deep = i;
            for(int j = 1; j <= n; ++j) {
                if(find(j) == find(i) && d[j] > d[deep])
                    deep = j;
            }
            int u = deep;
            while(1) {
                if(pp[u] == -1 || find(u) != find(pp[u]))
                    break;
                now.pb(u);
                u = pp[u];
            }
            solve_for_cycle();
            break;
        }
    }
    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:146:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:151:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:154:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:167: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:179:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 20480 KB Output is correct
2 Correct 12 ms 20520 KB Output is correct
3 Correct 14 ms 20608 KB Output is correct
4 Correct 203 ms 36344 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 14 ms 20608 KB Output is correct
13 Correct 151 ms 33032 KB Output is correct
14 Correct 178 ms 35448 KB Output is correct
15 Correct 194 ms 36344 KB Output is correct
16 Correct 153 ms 33912 KB Output is correct
17 Correct 196 ms 36300 KB Output is correct
18 Correct 242 ms 36344 KB Output is correct
19 Correct 247 ms 38136 KB Output is correct
20 Correct 15 ms 20384 KB Output is correct
21 Correct 14 ms 20608 KB Output is correct
22 Correct 194 ms 36344 KB Output is correct
23 Correct 150 ms 33060 KB Output is correct
24 Correct 230 ms 36472 KB Output is correct
25 Correct 201 ms 33784 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 20480 KB Output isn't correct
2 Incorrect 12 ms 20608 KB Output isn't correct
3 Correct 69 ms 29048 KB Output is correct
4 Incorrect 150 ms 40184 KB Output isn't correct
5 Correct 163 ms 35448 KB Output is correct
6 Correct 340 ms 43000 KB Output is correct
7 Incorrect 12 ms 20480 KB Output isn't correct
8 Incorrect 13 ms 20480 KB Output isn't correct
9 Correct 12 ms 19968 KB Output is correct
10 Correct 12 ms 20480 KB Output is correct
11 Incorrect 11 ms 20480 KB Output isn't correct
12 Correct 11 ms 20480 KB Output is correct
13 Correct 11 ms 19968 KB Output is correct
14 Incorrect 13 ms 20480 KB Output isn't correct
15 Incorrect 14 ms 20608 KB Output isn't correct
16 Incorrect 16 ms 20608 KB Output isn't correct
17 Correct 15 ms 20096 KB Output is correct
18 Correct 12 ms 20608 KB Output is correct
19 Incorrect 14 ms 20608 KB Output isn't correct
20 Correct 12 ms 20608 KB Output is correct
21 Correct 11 ms 20096 KB Output is correct
22 Incorrect 12 ms 20608 KB Output isn't correct
23 Incorrect 125 ms 35192 KB Output isn't correct
24 Incorrect 167 ms 38192 KB Output isn't correct
25 Correct 67 ms 29048 KB Output is correct
26 Correct 134 ms 38520 KB Output is correct
27 Incorrect 141 ms 38648 KB Output isn't correct
28 Correct 178 ms 36072 KB Output is correct
29 Correct 216 ms 38648 KB Output is correct
30 Incorrect 171 ms 39160 KB Output isn't correct
31 Incorrect 176 ms 40788 KB Output isn't correct
32 Incorrect 199 ms 36600 KB Output isn't correct
33 Correct 70 ms 29944 KB Output is correct
34 Correct 127 ms 38136 KB Output is correct
35 Incorrect 150 ms 40208 KB Output isn't correct
36 Correct 163 ms 35832 KB Output is correct
37 Correct 277 ms 43128 KB Output is correct
38 Incorrect 167 ms 39592 KB Output isn't correct
39 Incorrect 244 ms 36472 KB Output isn't correct
40 Incorrect 184 ms 37880 KB Output isn't correct
41 Correct 90 ms 31224 KB Output is correct
42 Correct 127 ms 38264 KB Output is correct
43 Incorrect 134 ms 40440 KB Output isn't correct
44 Correct 167 ms 35452 KB Output is correct
45 Correct 176 ms 39780 KB Output is correct
46 Incorrect 170 ms 39800 KB Output isn't correct
47 Incorrect 172 ms 38008 KB Output isn't correct
48 Incorrect 151 ms 40696 KB Output isn't correct
49 Correct 70 ms 27896 KB Output is correct
50 Correct 140 ms 38236 KB Output is correct
51 Incorrect 166 ms 37240 KB Output isn't correct
52 Correct 131 ms 36472 KB Output is correct
53 Correct 207 ms 39800 KB Output is correct
54 Incorrect 174 ms 39004 KB Output isn't correct