Submission #297030

#	Time	Username	Problem	Language	Result	Execution time	Memory
297030		Aldas25	늑대인간 (IOI18_werewolf)	C++14	49 / 100	4043 ms	61080 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAXN = 200100, MAXK = 20;

bool vis[MAXN];
bool ok = false;
vi adj[MAXN];
int cnt[MAXN];

void dfs (int v, int l, int r) {
    vis[v] = true;
    cnt[v]++;
    for (int u : adj[v]) {
        if (l <= u && u <= r && !vis[u])
            dfs(u, l, r);
    }
}

int toId[MAXN];

int minST[MAXN][MAXK];
int maxST[MAXN][MAXK];
int lg[MAXN];
int n;

void precLine () {
    int cur = 0;
    FOR(i, 0, n-1) if ((int)adj[i].size() == 1) cur = i;
    vi seq;
    seq.pb(cur);
    int p = -1;
    while (true) {
        int np = cur;
        int ncur = -1;
        for (int x : adj[cur])
            if (x != p)
                ncur = x;
        if (ncur == -1) break;
        cur = ncur;
        p = np;
        seq.pb(cur);
    }

    //cout << " seq: ";
    //for (int x : seq) cout << x << " ";
    //cout << endl;

    FOR(i, 0, n-1) toId[seq[i]] = i;

    FOR(i, 0, n-1) minST[i][0] = maxST[i][0] = seq[i];

    lg[1] = 0;
    FOR(i, 2, MAXN-1) lg[i] = lg[i/2] + 1;

    FOR(k, 1, MAXK-1) for (int i = 0; i + (1<<k) <= n; i++) {
        minST[i][k] = min(minST[i][k-1], minST[i + (1<<(k-1))][k-1]);
        maxST[i][k] = max(maxST[i][k-1], maxST[i + (1<<(k-1))][k-1]);
    }
}

int getMin (int le, int ri) {
    int k = lg[ri-le+1];
    return min(minST[le][k], minST[ri - (1<<k) + 1][k]);
}

int getMax (int le, int ri) {
    int k = lg[ri-le+1];
    return max(maxST[le][k], maxST[ri - (1<<k) + 1][k]);

}

std::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) {
    int Q = S.size();
    n = N;
    int m = (int)X.size();
    std::vector<int> A(Q);
    FOR(i, 0, m-1) {
        int u = X[i], v = Y[i];
        adj[u].pb(v);
        adj[v].pb(u);
    }

    bool s3 = true;
    if (m != n-1) s3 = false;
    FOR(i, 0, n-1) if ((int)adj[i].size() > 2) s3 = false;

    if (s3) {
        precLine ();
        //FOR(i, 0, n-1) FOR(j, i, n-1) cout << "  [" << i << ", " <<j<<"]  min: " << getMin(i,j) << " max: " << getMax(i,j) << endl;
        FOR(i, 0, Q-1) {
            int fr1, to1, fr2, to2;
            int le, ri;

           // cout << "     i = " << i << " S = " << S[i] << " E = " << E[i] << " L ="  << L[i] << " R = " << R[i] << endl;

            le = 0, ri = toId[S[i]];
            while (le < ri) {
                int mid = (le+ri)/2;
                if (getMin(mid, toId[S[i]]) < L[i]) le = mid+1;
                else ri = mid;
                //cout << " mid = " << mid << " getmin = " << getMin(mid, toId[S[i]]) << " le = " << le << " ri=" << ri << endl;
            }
            fr1 = le;

            le = toId[S[i]], ri = n-1;
            while (le < ri) {
                int mid = (le+ri+1)/2;
                if (getMin(toId[S[i]], mid) < L[i]) ri = mid-1;
                else le = mid;
            }
            to1 = le;



            le = 0, ri = toId[E[i]];
            while (le < ri) {
                int mid = (le+ri)/2;
                if (getMax(mid, toId[E[i]]) > R[i]) le = mid+1;
                else ri = mid;
                //cout << " mid = " << mid << " getmax = " << getMax(mid, toId[E[i]]) << " le = " << le << " ri=" << ri << endl;
            }
            fr2 = le;

            le = toId[E[i]], ri = n-1;
            while (le < ri) {
                int mid = (le+ri+1)/2;
                if (getMax(toId[E[i]], mid) > R[i]) ri = mid-1;
                else le = mid;
            }
            to2 = le;

            //cout << " fr1 = " << fr1 << " to1 = " << to1 << "  fr2 = " << fr2 << " to2 = " << to2 << endl;

            A[i] = (fr1 <= to2) && (fr2 <= to1);

        }

    } else {

        for (int i = 0; i < Q; ++i) {
            ok = false;
            FOR(j, 0, n-1) cnt[j] = 0;
            FOR(j, 0, n-1) vis[j] = 0;
            dfs (S[i], L[i], n-1);
            FOR(j, 0, n-1) vis[j] = 0;
            dfs (E[i], 0, R[i]);
            FOR(j, 0, n-1) if (cnt[j] > 1) ok  = true;
            A[i] = ok;
            //cout << "  ans: " << A[i] << endl;
        }
    }
    return A;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51