Submission #1276762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276762		uzukishinobu	Werewolf (IOI18_werewolf)	C++20	15 / 100	292 ms	83188 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int a,b;
pair<int,int> edge[1000005];
vector<int> z[1000005][2];
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);
}

int root1,root2,tour1,tour2;
int rev[200005][2];
struct dsu{
      int par[200005];
      int root;
      void init(){
          for (int i=1;i<=a;i++){
               par[i]=i;
          }

      }
      int find(int u){
          if (par[u]==u){
             return u;
          }
          return par[u]=find(par[u]);
      }
      void join(int x,int y,int t){
          x=find(x);
          y=find(y);
          if (x==y){
              return;
          }
          z[x][t].push_back(y);
          root=x;
          par[y]=x;
      }
};
dsu d;

int par[200005][21][2];
int sta[1000005][2];
int fin[1000005][2];
int tour;

void dfs(int i,int t){
    tour++;
    sta[i][t]=tour;
    rev[tour][t]=i;
    for (auto p:z[i][t]){
         par[p][0][t]=i;
         dfs(p,t);
    }
    fin[i][t]=tour;
}
struct node{
     int l,r,base,id;
};
vector<node> pos[1000005];
int res[100005];
int bit[400005];

void update(int i,int val){
    i++;
    while (i<=a+64){
         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> ans;
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();
    ans.resize(q);
     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]++;
    }
    for (int i=0;i<b;i++){
         edge[i]={X[i],Y[i]};
    }
    sort(edge,edge+b,cmp);
    d.init();
    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);
    }
    root1=d.root;
    sort(edge,edge+b,cmp1);
    d.init();
    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);
    }
    root2=d.root;
    dfs(root2,1);
    tour=0;
    dfs(root1,0);

    for (int j=1;j<=20;j++){
         for (int i=1;i<=a;i++){
              par[i][j][0]=par[par[i][j-1][0]][j-1][0];
              par[i][j][1]=par[par[i][j-1][1]][j-1][1];
         }
    }
    for (int i=0;i<q;i++){
         int x=S[i];
         int y=E[i];
         int l=L[i];
         int r=R[i];
         for (int j=20;j>=0;j--){
              if (par[x][j][1]>=l){
                  x=par[x][j][1];
              }
              if (par[y][j][0]<=r  && par[y][j][0]!=0){
                  y=par[y][j][0];
              }
         }
         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=0;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));
         }
    }
    for (int i=0;i<q;i++){
         ans[i]=(res[i]>0);
    }
    return ans;
}

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