oj.uz

답안 #968292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968292 2024-04-23T09:38:16 Z VinhLuu 늑대인간 (IOI18_werewolf) C++17
100 / 100
 658 ms 215168 KB 
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
//const int mod = 1e9 + 7;
//const int oo = 1e9;

int n, q, cal[N], ans[N];
vector<int> p[N];

struct tree{
    int pa[N], sz[N], Min[N], Max[N], in[N], en[N], demin, be[N], f[N][22];
    vector<int> g[N];
    void pre(){
        for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1, Max[i] = Min[i] = i;
    }
    int fin(int u){
        return pa[u] == u ? u : pa[u] = fin(pa[u]);
    }
    bool dsu(int x,int y){
        x = fin(x);
        y = fin(y);
        if(x == y) return 0;
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        pa[y] = x;
        Max[x] = max(Max[x], Max[y]);
        Min[x] = min(Min[x], Min[y]);
        return 1;
    }
    void dfs(int u,int v){
        in[u] = ++demin;
        if(v == 0) for(int i = 0; i <= 18; i ++) f[u][i] = u;
        else{
            f[u][0] = v;
            for(int i = 1; i <= 18; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
        }
        be[demin] = u;
        for(auto j : g[u]){
            if(j == v) continue;
            dfs(j, u);
        }
        en[u] = demin;
    }
    bool kt(int u,int v){
        return in[u] <= in[v] && in[v] <= en[u];
    }
    int Find(int type, int x,int lim){
        if(type == 0){
            int kq = x;
            for(int i = 18; i >= 0; i --) if(f[x][i] <= lim){
                kq = f[x][i];
                x = f[x][i];
            }
            return kq;
        }else{
            int kq = x;
            for(int i = 18; i >= 0; i --) if(f[x][i] >= lim){
                kq = f[x][i];
                x = f[x][i];
            }
            return kq;
        }
    }
} T[2];

int st[N << 1];

void update(int x){
    x += n - 1;
    st[x]++;
    while(x > 1){
        x /= 2;
        st[x]++;
    }
}

int get(int l,int r){
    r++;
    int ret = 0;
    for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
        if(l & 1) ret += st[l++];
        if(r & 1) ret += st[--r];
    }
    return ret;
}

vector<pii> open[N], close[N];

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, q = L.size();
    for(int i = 0; i < X.size(); i ++){
        int x = ++X[i], y = ++Y[i];
        p[x].pb(y);
        p[y].pb(x);
    }
    T[0].pre(), T[1].pre();
    for(int i = 1; i <= n; i ++) for(auto j : p[i]) if(j < i){
        int tmp = T[0].Max[T[0].fin(j)];
        if(T[0].dsu(i, j)){
            T[0].g[i].pb(tmp);
        }
    }
    T[0].dfs(n, 0);
    for(int i = n; i >= 1; i --) for(auto j : p[i]) if(j > i){
        int tmp = T[1].Min[T[1].fin(j)];
        if(T[1].dsu(i, j)){
            T[1].g[i].pb(tmp);
        }
    }
    T[1].dfs(1, 0);
    for(int i = 0; i < q; i ++){
        int s = ++S[i], e = ++E[i], l = ++L[i], r = ++R[i];
        if(e > R[i] || s < l){
            ans[i] = 0;
            continue;
        }
        int ce = T[0].Find(0, e, r), cs = T[1].Find(1, s, l);
        open[T[0].in[ce] - 1].pb({i, cs});
        close[T[0].en[ce]].pb({i, cs});
    }

    for(int i = 1; i <= n; i ++){
        int u = T[0].be[i];
        update(T[1].in[u]);
        for(auto [id, j] : open[i]) cal[id] -= get(T[1].in[j], T[1].en[j]);

        for(auto [id, j] : close[i]) cal[id] += get(T[1].in[j], T[1].en[j]);

    }
    vector<int> out;
    for(int i = 0; i < q; i ++){
//        cerr << cal[i] << " ";
        if(!cal[i]) out.pb(0);
        else out.pb(1);
    }
//    cerr << "h\n";
    return out;
}

//#define lpv
#ifdef lpv

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

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

    vector<int> x, y, st, ed, lf, rt;
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= m; i ++){
        int gg, hh; cin >> gg >> hh;
        x.pb(gg),y.pb(hh);
    }

    for(int i = 1; i <= q; i ++){
        int g, h, j, k; cin >> g >> h >> j >> k;
        st.pb(g), ed.pb(h), lf.pb(j), rt.pb(k);
    }
    vector<int> oo = check_validity(n,x,y,st,ed,lf,rt);
    for(auto j : oo) cout << j << "\n";
}

#endif // lpv

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 0; i < X.size(); i ++){
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 117864 KB Output is correct
2 Correct 33 ms 123740 KB Output is correct
3 Correct 57 ms 117980 KB Output is correct
4 Correct 52 ms 118248 KB Output is correct
5 Correct 54 ms 117840 KB Output is correct
6 Correct 57 ms 146936 KB Output is correct
7 Correct 54 ms 117840 KB Output is correct
8 Correct 51 ms 118020 KB Output is correct
9 Correct 51 ms 117840 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 117864 KB Output is correct
2 Correct 33 ms 123740 KB Output is correct
3 Correct 57 ms 117980 KB Output is correct
4 Correct 52 ms 118248 KB Output is correct
5 Correct 54 ms 117840 KB Output is correct
6 Correct 57 ms 146936 KB Output is correct
7 Correct 54 ms 117840 KB Output is correct
8 Correct 51 ms 118020 KB Output is correct
9 Correct 51 ms 117840 KB Output is correct
10 Correct 38 ms 125144 KB Output is correct
11 Correct 58 ms 119168 KB Output is correct
12 Correct 57 ms 119240 KB Output is correct
13 Correct 65 ms 119380 KB Output is correct
14 Correct 42 ms 125008 KB Output is correct
15 Correct 48 ms 124752 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 210708 KB Output is correct
2 Correct 658 ms 207796 KB Output is correct
3 Correct 557 ms 207820 KB Output is correct
4 Correct 437 ms 207076 KB Output is correct
5 Correct 468 ms 207436 KB Output is correct
6 Correct 476 ms 207964 KB Output is correct
7 Correct 492 ms 206924 KB Output is correct
8 Correct 515 ms 210164 KB Output is correct
9 Correct 393 ms 208312 KB Output is correct
10 Correct 381 ms 206584 KB Output is correct
11 Correct 375 ms 207088 KB Output is correct
12 Correct 402 ms 206704 KB Output is correct
13 Correct 616 ms 215028 KB Output is correct
14 Correct 603 ms 215164 KB Output is correct
15 Correct 600 ms 215060 KB Output is correct
16 Correct 634 ms 215168 KB Output is correct
17 Correct 474 ms 206988 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 117864 KB Output is correct
2 Correct 33 ms 123740 KB Output is correct
3 Correct 57 ms 117980 KB Output is correct
4 Correct 52 ms 118248 KB Output is correct
5 Correct 54 ms 117840 KB Output is correct
6 Correct 57 ms 146936 KB Output is correct
7 Correct 54 ms 117840 KB Output is correct
8 Correct 51 ms 118020 KB Output is correct
9 Correct 51 ms 117840 KB Output is correct
10 Correct 38 ms 125144 KB Output is correct
11 Correct 58 ms 119168 KB Output is correct
12 Correct 57 ms 119240 KB Output is correct
13 Correct 65 ms 119380 KB Output is correct
14 Correct 42 ms 125008 KB Output is correct
15 Correct 48 ms 124752 KB Output is correct
16 Correct 634 ms 210708 KB Output is correct
17 Correct 658 ms 207796 KB Output is correct
18 Correct 557 ms 207820 KB Output is correct
19 Correct 437 ms 207076 KB Output is correct
20 Correct 468 ms 207436 KB Output is correct
21 Correct 476 ms 207964 KB Output is correct
22 Correct 492 ms 206924 KB Output is correct
23 Correct 515 ms 210164 KB Output is correct
24 Correct 393 ms 208312 KB Output is correct
25 Correct 381 ms 206584 KB Output is correct
26 Correct 375 ms 207088 KB Output is correct
27 Correct 402 ms 206704 KB Output is correct
28 Correct 616 ms 215028 KB Output is correct
29 Correct 603 ms 215164 KB Output is correct
30 Correct 600 ms 215060 KB Output is correct
31 Correct 634 ms 215168 KB Output is correct
32 Correct 474 ms 206988 KB Output is correct
33 Correct 569 ms 208844 KB Output is correct
34 Correct 236 ms 158292 KB Output is correct
35 Correct 628 ms 211264 KB Output is correct
36 Correct 542 ms 207068 KB Output is correct
37 Correct 581 ms 207984 KB Output is correct
38 Correct 571 ms 207552 KB Output is correct
39 Correct 510 ms 213708 KB Output is correct
40 Correct 600 ms 213192 KB Output is correct
41 Correct 436 ms 206032 KB Output is correct
42 Correct 412 ms 204988 KB Output is correct
43 Correct 584 ms 211912 KB Output is correct
44 Correct 499 ms 207192 KB Output is correct
45 Correct 474 ms 214804 KB Output is correct
46 Correct 466 ms 209828 KB Output is correct
47 Correct 569 ms 209468 KB Output is correct
48 Correct 609 ms 209388 KB Output is correct
49 Correct 595 ms 209984 KB Output is correct
50 Correct 608 ms 212012 KB Output is correct
51 Correct 542 ms 210384 KB Output is correct
52 Correct 514 ms 210428 KB Output is correct