Submission #1276766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276766		uzukishinobu	Werewolf (IOI18_werewolf)	C++20	100 / 100	457 ms	98660 KiB

werewolf

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

const int MAXA = 1000005;
const int MAXV = 400005;
int a,b;
pair<int,int> edge[MAXA];
vector<int> z[MAXV][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;
int rev[MAXV][2];
struct dsu{
      int par[MAXV];
      int root;
      void init(int n){
          for (int i=1;i<=n;i++) par[i]=i;
          root = 0;
      }
      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 parA[MAXV][21][2];
int sta[MAXV][2];
int finA[MAXV][2];
int tour;

void dfs(int i,int t){
    if (i==0) return;
    tour++;
    sta[i][t]=tour;
    rev[tour][t]=i;
    for (auto p: z[i][t]){
         parA[p][0][t]=i;
         dfs(p,t);
    }
    finA[i][t]=tour;
}

struct node{
     int l,r,base,id;
};
vector<node> pos[MAXV];
int resArr[MAXV];
int bit[MAXV];

void update(int i,int val){
    while (i < MAXV){
         bit[i] += val;
         i += i & -i;
    }
}
int query(int 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 = (int)L.size();
    ans.assign(q, 0);
    a = N;
    b = (int)X.size();

    for (int i=0;i<=a+5 && i<MAXV;i++){
        z[i][0].clear();
        z[i][1].clear();
        pos[i].clear();
        resArr[i]=0;
        sta[i][0]=sta[i][1]=0;
        finA[i][0]=finA[i][1]=0;
        for (int j=0;j<21;j++){
            parA[i][j][0]=parA[i][j][1]=0;
        }
        rev[i][0]=rev[i][1]=0;
        bit[i]=0;
    }

    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(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);
    }
    root1 = d.root;
    sort(edge, edge + b, 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);
    }
    root2 = d.root;

    tour = 0;
    if (root2 != 0) dfs(root2, 1);
    tour = 0;
    if (root1 != 0) dfs(root1, 0);

    for (int j=1;j<=20;j++){
         for (int i=1;i<=a;i++){
              int up0 = parA[i][j-1][0];
              int up1 = parA[i][j-1][1];
              parA[i][j][0] = (up0>0 ? parA[up0][j-1][0] : 0);
              parA[i][j][1] = (up1>0 ? parA[up1][j-1][1] : 0);
         }
    }

    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 (parA[x][j][1] >= l && parA[x][j][1] != 0) x = parA[x][j][1];
              if (parA[y][j][0] != 0 && parA[y][j][0] <= r) y = parA[y][j][0];
         }
         if (sta[x][1] == 0 || sta[y][0] == 0) continue;
         pos[sta[x][1]-1].push_back({sta[y][0], finA[y][0], -1, i});
         pos[finA[x][1]].push_back({sta[y][0], finA[y][0], 1, i});
    }

    int maxTour1 = 0;
    for (int i=1;i<=a;i++) if (sta[i][1] > maxTour1) maxTour1 = sta[i][1];

    for (int i=0;i<=maxTour1;i++){
         if (rev[i][1] != 0 && sta[rev[i][1]][0] != 0){
             update(sta[rev[i][1]][0], 1);
         }
         for (auto &p: pos[i]){
              int add = query(p.r) - query(p.l - 1);
              resArr[p.id] += p.base * add;
         }
    }

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

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