Submission #1276764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276764		uzukishinobu	Werewolf (IOI18_werewolf)	C++20	0 / 100	305 ms	84276 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

int a;
struct dsu{
    vector<int> par;
    int root;
    void init(int n){
        par.assign(n+1,0);
        for (int i=1;i<=n;i++) par[i]=i;
        root=1;
    }
    int find(int u){
        if (par[u]==u) return u;
        return par[u]=find(par[u]);
    }
    void join(int x,int y,int t,vector<vector<int>>& z){
        x=find(x); y=find(y);
        if (x==y) return;
        z[x].push_back(y);
        root=x;
        par[y]=x;
    }
} d;

struct node{
    int l,r,base,id;
};

int root1,root2,tour;
vector<array<int,2>> rev,sta,fin;
vector<array<int,21>> par0,par1;
vector<vector<int>> z0,z1;
vector<vector<node>> pos;
vector<int> res;
vector<int> bit;

bool cmp(pair<int,int> a,pair<int,int> b){
    return max(a.first,a.second)<max(b.first,b.second);
}
bool cmp1(pair<int,int> a,pair<int,int> b){
    return min(a.first,a.second)>min(b.first,b.second);
}

void dfs(int i,int t,vector<vector<int>>& z,vector<array<int,2>>& sta,vector<array<int,2>>& fin,vector<array<int,2>>& rev,vector<array<int,21>>& par){
    tour++;
    sta[i][t]=tour;
    rev[tour][t]=i;
    for (auto p:z[i]){
        if (t==0) par[p][0]=par[i][0]; 
        else par[p][0]=par[i][0];
        dfs(p,t,z,sta,fin,rev,par);
    }
    fin[i][t]=tour;
}

void update(int i,int val){
    i++;
    while (i<(int)bit.size()){
        bit[i]+=val;
        i+=i&-i;
    }
}
int query(int i){
    i++;
    int res=0;
    while (i>0){
        res+=bit[i];
        i-=i&-i;
    }
    return res;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
    int q=L.size();
    a=N;
    int b=X.size();
    for (int i=0;i<b;i++){ X[i]++; Y[i]++; }
    for (int i=0;i<q;i++){ L[i]++; R[i]++; S[i]++; E[i]++; }
    vector<pair<int,int>> edge(b);
    for (int i=0;i<b;i++) edge[i]={X[i],Y[i]};
    z0.assign(a+5,{}); z1.assign(a+5,{});
    rev.assign(a+5,{0,0});
    sta.assign(a+5,{0,0});
    fin.assign(a+5,{0,0});
    par0.assign(a+5,{0}); par1.assign(a+5,{0});
    pos.assign(a+5,{});
    res.assign(q,0);
    bit.assign(a+200,0);
    sort(edge.begin(),edge.end(),cmp);
    d.init(a);
    for (int i=0;i<b;i++){
        int u=max(edge[i].first,edge[i].second);
        int v=min(edge[i].first,edge[i].second);
        d.join(u,v,0,z0);
    }
    root1=d.root;
    sort(edge.begin(),edge.end(),cmp1);
    d.init(a);
    for (int i=0;i<b;i++){
        int u=min(edge[i].first,edge[i].second);
        int v=max(edge[i].first,edge[i].second);
        d.join(u,v,1,z1);
    }
    root2=d.root;
    tour=0;
    dfs(root2,1,z1,sta,fin,rev,par1);
    tour=0;
    dfs(root1,0,z0,sta,fin,rev,par0);
    for (int j=1;j<=20;j++){
        for (int i=1;i<=a;i++){
            if (par0[i][j-1]) par0[i][j]=par0[par0[i][j-1]][j-1];
            if (par1[i][j-1]) par1[i][j]=par1[par1[i][j-1]][j-1];
        }
    }
    for (int i=0;i<q;i++){
        int x=S[i],y=E[i],l=L[i],r=R[i];
        for (int j=20;j>=0;j--){
            if (par1[x][j]>=l) x=par1[x][j];
            if (par0[y][j]<=r && par0[y][j]!=0) y=par0[y][j];
        }
        pos[sta[x][1]-1].push_back({sta[y][0],fin[y][0],-1,i});
        pos[fin[x][1]].push_back({sta[y][0],fin[y][0],1,i});
    }
    for (int i=1;i<=a;i++){
        update(sta[rev[i][1]][0],1);
        for (auto p:pos[i]){
            res[p.id]+=p.base*(query(p.r)-query(p.l-1));
        }
    }
    vector<int> ans(q);
    for (int i=0;i<q;i++) ans[i]=(res[i]>0);
    return ans;
}

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