oj.uz

답안 #1020168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020168 2024-07-11T16:14:47 Z Issa 늑대인간 (IOI18_werewolf) C++17
15 / 100
 132 ms 73812 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e3 + 100;

int n;
int pref[maxn][maxn];
int suf[maxn][maxn];
vector<int> g[maxn];

int get(int v, int p[]){
    if(p[v] == v) return v;
    return p[v] = get(p[v], p);
}

void join(int a, int b, int p[]){
    p[get(a, p)] = get(b, p);
}

void add(vector<int> &v){
    for(int &x: v) x++;
}

int mx[22][maxn];
int mn[22][maxn];
int b[maxn], t;
int lg[maxn];

void dfs(int v, int p = 0){
    t++; b[v] = t;
    mx[0][t] = mn[0][t] = v;
    for(int to: g[v]){
        if(to == p) continue;
        dfs(to, v);
    }
}

int getmn(int l, int r){
    int k = lg[r - l + 1];
    return min(mn[l][k], mn[r-(1<<k)+1][k]);
}

int getmx(int l, int r){
    int k = lg[r - l + 1];
    return max(mx[l][k], mx[r-(1<<k)+1][k]);
}

vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R){
    add(X); add(Y); add(S); add(E); add(L); add(R); n = N;
    for(int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    if(n <= 3000){
        for(int i = 1; i <= n; i++){
            pref[0][i] = suf[n+1][i] = i;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                pref[i][j] = pref[i-1][j];
            }
            for(int to: g[i]){
                if(to < i) join(to, i, pref[i]);
            }
        }
        for(int i = n; i > 0; i--){
            for(int j = 1; j <= n; j++){
                suf[i][j] = suf[i+1][j];
            }
            for(int to: g[i]){
                if(to > i) join(to, i, suf[i]);
            }
        }
        vector<int> ans;
        for(int i = 0; i < S.size(); i++){
            int s = S[i], e = E[i];
            int l = L[i], r = R[i];
            int res = 0;
            for(int k = l; k <= r; k++){
                if(get(s, suf[l]) == get(k, suf[l]) && get(k, pref[r]) == get(e, pref[r])){
                    res = 1;
                }
            }
            ans.push_back(res);
        }
        return ans;
    } else{
        for(int i = 1; i <= n; i++){
            if(g[i].size() == 1) dfs(i);
            if(i > 1) lg[i] = lg[i >> 1] + 1;
        }
        for(int k = 1; k <= lg[n]; k++){
            for(int i = 1; i + (1<<k) - 1 <= n; i++){
                mx[k][i] = max(mx[k-1][i], mx[k-1][i+(1<<(k-1))]);
                mn[k][i] = min(mn[k-1][i], mn[k-1][i+(1<<(k-1))]);
            }
        }
        vector<int> ans;
        for(int i = 0; i < S.size(); i++){
            int s = S[i], e = E[i];
            int l = L[i], r = R[i];
            s = b[s]; e = b[e];
            int res = 0;
            if(s <= e){
                int tr = s - 1, tl = e + 1;
                for(int bl = s, br = e; bl <= br;){
                    int mid = (bl + br) >> 1;
                    if(getmn(s, mid) < l) br = mid - 1;
                    else bl = mid + 1, tr = mid;
                }
                for(int bl = s, br = e; bl <= br;){
                    int mid = (bl + br) >> 1;
                    if(getmx(mid, e) > r) bl = mid + 1;
                    else br = mid - 1, tl = mid;
                }
                if(tl <= tr) res = 1;
            } else{
                int tr = e - 1, tl = s + 1;
                for(int bl = e, br = s; bl <= br;){
                    int mid = (bl + br) >> 1;
                    if(getmn(mid, s) < l) br = mid - 1;
                    else bl = mid + 1, tr = mid;
                }
                for(int bl = e, br = s; bl <= br;){
                    int mid = (bl + br) >> 1;
                    if(getmx(e, mid) > r) bl = mid + 1;
                    else br = mid - 1, tl = mid;
                }
                if(tl <= tr) res = 1;
            }
            ans.push_back(res);
        }
        return ans;
    }
}

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:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < X.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i = 0; i < S.size(); i++){
      |                        ~~^~~~~~~~~~
werewolf.cpp:101:26: 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 < S.size(); i++){
      |                        ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 1292 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1352 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 1292 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1352 KB Output is correct
10 Correct 95 ms 73556 KB Output is correct
11 Correct 113 ms 73672 KB Output is correct
12 Correct 71 ms 73812 KB Output is correct
13 Correct 80 ms 73552 KB Output is correct
14 Correct 68 ms 73552 KB Output is correct
15 Correct 83 ms 73812 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 132 ms 50768 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 1292 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1352 KB Output is correct
10 Correct 95 ms 73556 KB Output is correct
11 Correct 113 ms 73672 KB Output is correct
12 Correct 71 ms 73812 KB Output is correct
13 Correct 80 ms 73552 KB Output is correct
14 Correct 68 ms 73552 KB Output is correct
15 Correct 83 ms 73812 KB Output is correct
16 Runtime error 132 ms 50768 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -