oj.uz

답안 #939526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939526 2024-03-06T12:55:09 Z Zero_OP 늑대인간 (IOI18_werewolf) C++14
100 / 100
 721 ms 133880 KB 
#include<bits/stdc++.h>

using namespace std;
using int64 = int64_t;

#define     REP(i, n) for(int i = 0, _n = n; i < _n; ++i)
#define    REPD(i, n) for(int i = n - 1; i >= 0; --i)
#define  FOR(i, l, r) for(int i = l, _r = r; i <= _r; ++i)
#define FORD(i, r, l) for(int i = r, _l = l; i >= _l; --i)
#define          left __left
#define         right __right
#define          prev __prev
#define          next __next
#define           div __div
#define            pb push_back
#define            pf push_front
#define         sz(v) (int)v.size()
#define      range(v) begin(v), end(v)
#define    compact(v) v.erase(unique(range(v)), end(v))
#define      debug(v) "[" #v " = " << (v) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            a = b;
            return true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            a = b;
            return true;
        }
        return false;
    }

template<int dimension, class T>
struct vec : public vector<vec<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>>(n, vec<dimension - 1, T>(args...)) {}
};

template<class T>
struct vec<1, T> : public vector<T> {
    vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};

const int MAXN = 2e5 + 5;
const int MAXM = 4e5 + 5;

int n, m, q, number_of_nodes, tin[MAXN + MAXM], tout[MAXN + MAXM];
int lab[MAXN + MAXM], human[MAXN], werewolf[MAXN];
int pos_human[MAXN], pos_werewolf[MAXN], a[MAXN];
int S[MAXN], E[MAXN], L[MAXN], R[MAXN];
int l1[MAXN], r1[MAXN], l2[MAXN], r2[MAXN];
vector<int> adj[MAXN], g[MAXN + MAXM], order, ask[MAXN], st[MAXN << 2];

int find_root(int u){
    return lab[u] < 0 ? u : (lab[u] = find_root(lab[u]));
}

void unite(int u, int v){
    u = find_root(u);
    v = find_root(v);
    if(u == v) return;
    g[number_of_nodes].pb(u);
    if(u != v) g[number_of_nodes].pb(v);
    lab[number_of_nodes] = lab[u] + lab[v];
    lab[u] = lab[v] = number_of_nodes;
    ++number_of_nodes;
}

void dfs_euler(int u){
    tin[u] = sz(order);
    for(int v : g[u]){
        dfs_euler(v);
    }
    if(u < n) order.pb(u);
    tout[u] = sz(order) - 1;
}

void reset(){
    order.clear();
    number_of_nodes = n;
    REP(i, n + m){
        g[i].clear();
        tin[i] = 0;
        tout[i] = 0;
        lab[i] = -1;
    }
}

void process_human(){
    reset();
    REP(i, q){
        ask[L[i]].pb(i);
    }

    REPD(i, n){
        for(int j : adj[i]){
            if(j >= i){
                unite(i, j);
            }
        }
        for(int id : ask[i]){
            human[id] = find_root(S[id]);
        }
        ask[i].clear();
    }

    dfs_euler(number_of_nodes - 1);
    REP(i, n){
        pos_human[i] = tin[i];
    }

    REP(i, q){
        l1[i] = tin[human[i]];
        r1[i] = tout[human[i]];
    }
}

void process_werewolf(){
    reset();
    REP(i, q){
        ask[R[i]].pb(i);
    }

    REP(i, n){
        for(int j : adj[i]){
            if(j <= i){
                unite(i, j);
            }
        }
        for(int id : ask[i]){
            werewolf[id] = find_root(E[id]);
        }
        ask[i].clear();
    }

    dfs_euler(number_of_nodes - 1);
    REP(i, n){
        pos_werewolf[i] = tin[i];
    }

    REP(i, q){
        l2[i] = tin[werewolf[i]];
        r2[i] = tout[werewolf[i]];
    }
}

void build(int id, int l, int r){
    if(l == r) st[id] = {a[l]};
    else{
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        merge(range(st[id << 1]), range(st[id << 1 | 1]), back_inserter(st[id]));
    }
}

int find_search(int u, int v, int at_least, int id = 1, int l = 0, int r = n - 1){
    if(v < l or u > r) return INT_MAX;
    if(u <= l && r <= v){
        auto iter = lower_bound(range(st[id]), at_least);
        return (iter == st[id].end() ? INT_MAX : *iter);
    }

    int mid = l + r >> 1;
    return min(find_search(u, v, at_least, id << 1, l, mid), find_search(u, v, at_least, id << 1 | 1, mid + 1, r));
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R){
    n = N;
    m = sz(X);
    q = sz(_S);

    REP(i, m){
        int u = X[i], v = Y[i];
        adj[u].pb(v);
        adj[v].pb(u);
    }


    REP(i, q){
        tie(S[i], E[i], L[i], R[i]) = make_tuple(_S[i], _E[i], _L[i], _R[i]);
    }

    process_human();
    process_werewolf();

    REP(i, n){
        a[pos_human[i]] = pos_werewolf[i];
    }

    build(1, 0, n - 1);
    vector<int> ans(q);
    REP(i, q){
        if(find_search(l1[i], r1[i], l2[i]) <= r2[i]){
            ans[i] = 1;
        }
        else ans[i] = 0;
    }

    return ans;
}

//#define Zero_OP //turn off when submitting
#ifdef Zero_OP

void init(void);
void process(void);

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define task "antuvu"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) {
        init();
        process();
    }

    return 0;
}

void init(){

}

void process(){
    vector<int> ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
    REP(i, sz(ans)) cout << ans[i] << ' '; cout << '\n';
}

#endif

Compilation message

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:158:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  158 |         int mid = l + r >> 1;
      |                   ~~^~~
werewolf.cpp: In function 'int find_search(int, int, int, int, int, int)':
werewolf.cpp:172:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 53852 KB Output is correct
2 Correct 12 ms 53852 KB Output is correct
3 Correct 12 ms 53852 KB Output is correct
4 Correct 11 ms 51804 KB Output is correct
5 Correct 11 ms 51980 KB Output is correct
6 Correct 12 ms 53852 KB Output is correct
7 Correct 11 ms 53940 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 11 ms 51804 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 53852 KB Output is correct
2 Correct 12 ms 53852 KB Output is correct
3 Correct 12 ms 53852 KB Output is correct
4 Correct 11 ms 51804 KB Output is correct
5 Correct 11 ms 51980 KB Output is correct
6 Correct 12 ms 53852 KB Output is correct
7 Correct 11 ms 53940 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 11 ms 51804 KB Output is correct
10 Correct 16 ms 54876 KB Output is correct
11 Correct 18 ms 54876 KB Output is correct
12 Correct 15 ms 52824 KB Output is correct
13 Correct 16 ms 53084 KB Output is correct
14 Correct 15 ms 54872 KB Output is correct
15 Correct 17 ms 54876 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 461 ms 115812 KB Output is correct
2 Correct 478 ms 128712 KB Output is correct
3 Correct 483 ms 125780 KB Output is correct
4 Correct 441 ms 124592 KB Output is correct
5 Correct 452 ms 124360 KB Output is correct
6 Correct 471 ms 124364 KB Output is correct
7 Correct 424 ms 122696 KB Output is correct
8 Correct 476 ms 128840 KB Output is correct
9 Correct 368 ms 125280 KB Output is correct
10 Correct 402 ms 124028 KB Output is correct
11 Correct 402 ms 123884 KB Output is correct
12 Correct 365 ms 124024 KB Output is correct
13 Correct 462 ms 128968 KB Output is correct
14 Correct 431 ms 128952 KB Output is correct
15 Correct 434 ms 128968 KB Output is correct
16 Correct 480 ms 128964 KB Output is correct
17 Correct 401 ms 122572 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 53852 KB Output is correct
2 Correct 12 ms 53852 KB Output is correct
3 Correct 12 ms 53852 KB Output is correct
4 Correct 11 ms 51804 KB Output is correct
5 Correct 11 ms 51980 KB Output is correct
6 Correct 12 ms 53852 KB Output is correct
7 Correct 11 ms 53940 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 11 ms 51804 KB Output is correct
10 Correct 16 ms 54876 KB Output is correct
11 Correct 18 ms 54876 KB Output is correct
12 Correct 15 ms 52824 KB Output is correct
13 Correct 16 ms 53084 KB Output is correct
14 Correct 15 ms 54872 KB Output is correct
15 Correct 17 ms 54876 KB Output is correct
16 Correct 461 ms 115812 KB Output is correct
17 Correct 478 ms 128712 KB Output is correct
18 Correct 483 ms 125780 KB Output is correct
19 Correct 441 ms 124592 KB Output is correct
20 Correct 452 ms 124360 KB Output is correct
21 Correct 471 ms 124364 KB Output is correct
22 Correct 424 ms 122696 KB Output is correct
23 Correct 476 ms 128840 KB Output is correct
24 Correct 368 ms 125280 KB Output is correct
25 Correct 402 ms 124028 KB Output is correct
26 Correct 402 ms 123884 KB Output is correct
27 Correct 365 ms 124024 KB Output is correct
28 Correct 462 ms 128968 KB Output is correct
29 Correct 431 ms 128952 KB Output is correct
30 Correct 434 ms 128968 KB Output is correct
31 Correct 480 ms 128964 KB Output is correct
32 Correct 401 ms 122572 KB Output is correct
33 Correct 614 ms 125652 KB Output is correct
34 Correct 211 ms 91800 KB Output is correct
35 Correct 650 ms 129024 KB Output is correct
36 Correct 515 ms 124872 KB Output is correct
37 Correct 605 ms 127952 KB Output is correct
38 Correct 565 ms 125636 KB Output is correct
39 Correct 448 ms 133880 KB Output is correct
40 Correct 481 ms 133080 KB Output is correct
41 Correct 543 ms 127444 KB Output is correct
42 Correct 447 ms 124332 KB Output is correct
43 Correct 721 ms 132996 KB Output is correct
44 Correct 592 ms 128072 KB Output is correct
45 Correct 572 ms 133832 KB Output is correct
46 Correct 660 ms 133584 KB Output is correct
47 Correct 442 ms 128964 KB Output is correct
48 Correct 413 ms 128880 KB Output is correct
49 Correct 462 ms 129220 KB Output is correct
50 Correct 426 ms 128956 KB Output is correct
51 Correct 499 ms 132036 KB Output is correct
52 Correct 466 ms 131832 KB Output is correct