제출 #120438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120438		songc	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4085 ms	44928 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, Q;
int P[404040], NL[404040], NR[404040], num;
int H[202020], W[202020];
int HS[202020], HE[202020];
int WS[202020], WE[202020];
vector<int> ans, C[404040];
vector<pii> Point;

struct Data{
    int t, u, v, w;
};
vector<Data> A;

int Find(int u){
    if (u == P[u]) return u;
    return P[u] = Find(P[u]);
}

void Union(int u, int v){
    int pu = Find(u);
    int pv = Find(v);
    if (pu == pv) return;
    P[pu] = P[pv] = num;
    NL[num] = NL[pu];
    NR[num] = NR[pv];
    C[num].push_back(pu);
    C[num].push_back(pv);
    num++;
}

void dfsH(int u){
    if (C[u].empty()){
        H[u] = num++;
        return;
    }
    dfsH(C[u][0]);
    dfsH(C[u][1]);
    C[u].clear();
}

void dfsW(int u){
    if (C[u].empty()){
        W[u] = num++;
        return;
    }
    dfsW(C[u][0]);
    dfsW(C[u][1]);
    C[u].clear();
}

struct Node{
    Node *lc, *rc;
    int val=0;
} *PST[202020];

void init(Node* now, int s, int e){
    if (s == e) return;
    int mid = (s+e)/2;
    now->lc = new Node;
    init(now->lc, s, mid);
    now->rc = new Node;
    init(now->rc, mid+1, e);
}

void update(Node* pre, Node* now, int s, int e, int t){
    now->val++;
    if (s == e) return;
    int mid = (s+e)/2;
    if (t <= mid){
        now->lc = new Node;
        update(pre->lc, now->lc, s, mid, t);
        now->rc = pre->rc;
    }
    else{
        now->lc = pre->lc;
        now->rc = new Node;
        update(pre->rc, now->rc, mid+1, e, t);
    }
}

int query(Node* now, int s, int e, int ts, int te){
    if (e < ts || te < s) return 0;
    if (ts <= s && e <= te) return now->val;
    int mid = (s+e)/2;
    return query(now->lc, s, mid, ts, te) + query(now->rc, mid+1, e, ts, te);
}

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 = X.size(), Q = S.size();

    for (int i=0; i<M; i++) A.push_back((Data){0, X[i], Y[i], min(X[i], Y[i])});
    for (int i=0; i<Q; i++) A.push_back((Data){1, S[i], i, L[i]});
    sort(A.begin(), A.end(), [&](Data a, Data b){
        if (a.w == b.w) return a.t < b.t;
        return a.w > b.w;
    });

    num = N+1;
    for (int i=0; i<=2*N; i++) P[i] = i, NL[i] = NR[i] = i;
    for (int i=0; i<(int)A.size(); i++){
        if (A[i].t == 0) Union(A[i].u, A[i].v);
        else {
            HS[A[i].v] = NL[Find(A[i].u)];
            HE[A[i].v] = NR[Find(A[i].u)];
        }
    }
    num=0;
    dfsH(2*N-1);
    A.clear();

    for (int i=0; i<M; i++) A.push_back((Data){0, X[i], Y[i], max(X[i], Y[i])});
    for (int i=0; i<Q; i++) A.push_back((Data){1, E[i], i, R[i]});
    sort(A.begin(), A.end(), [&](Data a, Data b){
        if (a.w == b.w) return a.t < b.t;
        return a.w < b.w;
    });

    num = N+1;
    for (int i=0; i<=2*N; i++) P[i] = i, NL[i] = NR[i] = i;
    for (int i=0; i<(int)A.size(); i++){
        if (A[i].t == 0) Union(A[i].u, A[i].v);
        else {
            WS[A[i].v] = NL[Find(A[i].u)];
            WE[A[i].v] = NR[Find(A[i].u)];
        }
    }
    num=0;
    dfsW(2*N-1);
    A.clear();

    for (int i=0; i<Q; i++){
        HS[i] = H[HS[i]], HE[i] = H[HE[i]];
        WS[i] = W[WS[i]], WE[i] = W[WE[i]];
    }
    for (int i=0; i<N; i++) Point.push_back(pii(H[i], W[i]));
    sort(Point.begin(), Point.end());
    /*
    PST[0] = new Node;
    init(PST[0], 1, N);
    for (int i=1; i<=N; i++) {
        PST[i] = new Node;
        update(PST[i-1], PST[i], 1, N, Point[i].second+1);
    }
    */

    for (int i=0; i<Q; i++){
        //if (query(PST[HE[i]+1], 1, N, WS[i]+1, WE[i]+1) - query(PST[HS[i]+1], 1, N, WS[i]+1, WE[i]+1)) ans.push_back(1);
        //else ans.push_back(0);
        bool tf = false;
        for (int j=0; j<N; j++){
            if (HS[i] <= Point[j].first && Point[j].first <= HE[i] && WS[i] <= Point[j].second && Point[j].second <= WE[i]) tf = true;
        }
        if (tf) ans.push_back(1);
        else ans.push_back(0);
    }
    return ans;
}

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