제출 #827026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827026		bachhoangxuan	Werewolf (IOI18_werewolf)	C++17	100 / 100	664 ms	100632 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int maxl=20;
#define pii pair<int,int>
#define piii pair<pii,int>
#define fi first
#define se second

int par[maxn];
int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}

struct Tree{
    vector<int> edge[maxn];
    int n,L[maxn],R[maxn],num,p[maxn][maxl];
    void add(int u,int v){
        par[v]=p[v][0]=u;
        edge[u].push_back(v);
    }
    void dfs(int u){
        L[u]=++num;
        for(int i=1;i<18;i++) p[u][i]=p[p[u][i-1]][i-1];
        for(int v:edge[u]) dfs(v);
        R[u]=num;
    }
    void build(vector<pii> e,int root){
        for(int i=1;i<=n;i++) par[i]=i;
        for(auto &[u,v]:e){
            u=findpar(u);v=findpar(v);
            if(u!=v) add(u,v);
        }
        dfs(root);
    }
    int get(int u,int l,int r){
        for(int i=17;i>=0;i--) if(p[u][i]>=l && p[u][i]<=r) u=p[u][i];
        return u;
    }
}T1,T2;

namespace BIT{
    int n,bit[maxn];
    void update(int x){
        for(int i=x;i<=n;i+=(i&(-i))) bit[i]++;
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
        return res;
    }
}

vector<int> check_validity(int N, vector<int> U, vector<int> V,
                                vector<int> s, vector<int> t,
                                vector<int> l, vector<int> r) {
    int m=(int)U.size();
    T1.n=T2.n=BIT::n=N;

    vector<pii> e;
    for(int i=0;i<m;i++){
        U[i]++;V[i]++;
        if(U[i]>V[i]) swap(U[i],V[i]);
        e.push_back({U[i],V[i]});
    }
    sort(e.begin(),e.end(),greater<pii>());
    T1.build(e,1);

    e.clear();
    for(int i=0;i<m;i++) e.push_back({V[i],U[i]});
    sort(e.begin(),e.end());
    T2.build(e,N);

    int q=(int)s.size();
    vector<int> ans(q);
    vector<piii> query;
    for(int i=1;i<=N;i++) query.push_back({{T1.L[i],T2.L[i]},-q-1});
    for(int i=0;i<q;i++){
        s[i]++;t[i]++;l[i]++;r[i]++;
        s[i]=T1.get(s[i],l[i],N);
        t[i]=T2.get(t[i],1,r[i]);
        query.push_back({{T1.R[s[i]],T2.R[t[i]]},i+1});
        query.push_back({{T1.L[s[i]]-1,T2.R[t[i]]},-i-1});
        query.push_back({{T1.R[s[i]],T2.L[t[i]]-1},-i-1});
        query.push_back({{T1.L[s[i]]-1,T2.L[t[i]]-1},i+1});
    }
    sort(query.begin(),query.end());
    for(auto &[d,id]:query){
        if(id==-q-1) BIT::update(d.se);
        else ans[abs(id)-1]+=(id<0?-1:1)*BIT::query(d.se);
    }

    for(int i=0;i<q;i++) ans[i]=(ans[i]>=1);
    return ans;
}

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