oj.uz

답안 #371513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371513 2021-02-26T19:45:36 Z thecodingwizard 늑대인간 (IOI18_werewolf) C++11
0 / 100
 4000 ms 80052 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

#define pi pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back

vector<int> adj[200000];
vector<int> adj2[200000];
int smallIdx[200000];
int smallStart[200000];
int smallEnd[200000];
int largeIdx[200000];
int largeStart[200000];
int largeEnd[200000];
int pa[200000];
int parSmall[200000][20];
int parLarge[200000][20];
int sz[200000];
int smallest[200000];
int largest[200000];

int ctr = 0;
void dfs(int u, int *idx, int *start, int *end) {
    start[u] = ctr;
    for (int v : adj2[u]) {
        dfs(v, idx, start, end);
    }
    end[u] = ctr;
    idx[u] = ctr++;
}

int get(int x) { return x == pa[x] ? x : pa[x] = get(pa[x]); }
void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    pa[a] = b;
    sz[b] += sz[a];
    if (smallest[b] > smallest[a]) {
        // put b as child of a
        adj2[smallest[a]].pb(smallest[b]);
        parSmall[smallest[b]][0] = smallest[a];
    } else {
        adj2[smallest[b]].pb(smallest[a]);
        parSmall[smallest[a]][0] = smallest[b];
    }
    smallest[b] = min(smallest[b], smallest[a]);
}
void unite2(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    pa[a] = b;
    sz[b] += sz[a];
    if (largest[b] < largest[a]) {
        // put b as child of a
        adj2[largest[a]].pb(largest[b]);
        parLarge[largest[b]][0] = largest[a];
    } else {
        adj2[largest[b]].pb(largest[a]);
        parLarge[largest[a]][0] = largest[b];
    }
    largest[b] = max(largest[b], largest[a]);
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    for (int i = 0; i < (int)X.size(); i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < n; i++) {
        pa[i] = i;
        sz[i] = 1;
        smallest[i] = i;
    }

    for (int i = n-1; ~i; i--) {
        for (int v : adj[i]) {
            if (v > i) {
                unite(v, i);
            }
        }
    }

    ctr = 0;
    dfs(0, smallIdx, smallStart, smallEnd);
    parSmall[0][0] = 0;

    for (int i = 0; i < n; i++) {
        pa[i] = i;
        sz[i] = 1;
        largest[i] = i;
        adj2[i].clear();
    }

    for (int i = 0; i < n; i++) {
        for (int v : adj[i]) {
            if (v < i) {
                unite2(v, i);
            }
        }
    }

    ctr = 0;
    dfs(n-1, largeIdx, largeStart, largeEnd);
    parLarge[n-1][n-1] = n-1;

    vector<int> A(S.size(), 0);

    for (int i = 0; i < (int)S.size(); i++) {
        int u = S[i];
        while (parSmall[u][0] >= L[i]) {
            u = parSmall[u][0];
            if (u == parSmall[u][0]) break;
        }
        int smallLeft = smallStart[u], smallRight = smallEnd[u];

        u = E[i];
        while (parLarge[u][0] <= R[i]) {
            u = parLarge[u][0];
            if (u == parLarge[u][0]) break;
        }
        int largeLeft = largeStart[u], largeRight = largeEnd[u];
        //cout << u << " " << smallLeft << " " << smallRight << " " << largeLeft << " " << largeRight << endl;


        for (int j = 0; j < n; j++) {
            if (largeLeft <= largeIdx[j] && largeIdx[j] <= largeRight) {
                if (smallLeft <= smallIdx[j] && smallIdx[j] <= smallRight) {
                    A[i] = 1;
                }
            }
        }
    }

    return A;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4058 ms 9836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4058 ms 9836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4091 ms 80052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4058 ms 9836 KB Time limit exceeded
2 Halted 0 ms 0 KB -