Submission #1276748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276748		uzukishinobu	Werewolf (IOI18_werewolf)	C++20	0 / 100	771 ms	172928 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int a,b;
vector<pair<int,int>> edge;
vector<vector<vector<int>>> z;
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);
}
vector<array<int,2>> val; 
const int LOG = 20;
vector<vector<array<int,2>>> up;
int root1,root2,tour1,tour2;
vector<array<int,2>> rev;
struct dsu{
      vector<int> par;
      vector<int> sz;
      int cur;
      void init(int _a, int sadge){
          cur = _a - 1;
          par.assign(sadge,0);
          for (int i=0;i<sadge;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;
           }
           cur++;
           val[cur][t]=val[x][t];
           z[cur][t].push_back(x);
           z[cur][t].push_back(y);
           par[y]=cur;
           par[x]=cur;
           up[x][0][t]=cur;
           up[y][0][t]=cur;
      }
};
dsu d;

vector<array<int,2>> sta; 
vector<array<int,2>> fin; 
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]){
         dfs(p,t);
    }
    fin[i][t]=tour;
}
struct node{
     int l,r,base,id;
};
vector<vector<node>> pos;
vector<int> res;
vector<int> bit;
int BITN;

void update(int i,int valx){
    i++;
    while (i<=BITN){
         bit[i]+=valx;
         i+=i&-i;
    }
}
int query(int i){
    if (i < 0) return 0;
    i++;
    int resq=0;
    while (i>0){
         resq+=bit[i];
         i-=i&-i;
    }
    return resq;
}

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 = S.size();
    vector<int> A(q);
    for (int i = 0; i < q; ++i) {
        A[i] = 0;
    }
    a=N;
    b=X.size();
    edge.assign(b, {0,0});
    for (int i=0;i<b;i++){
         edge[i]={X[i],Y[i]};
    }

    int sadge = a + b + 5;
    if (sadge < a+5) sadge = a + 5;

    z.assign(sadge, vector<vector<int>>(2));
    val.assign(sadge, {0,0});
    up.assign(sadge, vector<array<int,2>>(LOG));
    sta.assign(sadge, {0,0});
    fin.assign(sadge, {0,0});
    rev.assign(sadge, {0,0});

    for (int i=0;i<a;i++){
         val[i][0]=val[i][1]=i;
    }
    for (int i=0;i<sadge;i++){
        for (int j=0;j<LOG;j++){
            up[i][j][0]=up[i][j][1]=0;
        }
    }

    sort(edge.begin(),edge.end(),cmp);
    d.init(a, sadge);
    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.cur;

    sort(edge.begin(),edge.end(),cmp1);

    d.init(a, sadge);
    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.cur;

    if (root1 >= 0) up[root1][0][0] = root1;
    if (root2 >= 0) up[root2][0][1] = root2;

    int maxNodeIndex = max(root1, root2);
    if (maxNodeIndex < a-1) maxNodeIndex = a-1;

    for (int i=0;i<=maxNodeIndex;i++){
        if (up[i][0][0] == 0 && i != root1) up[i][0][0] = i;
        if (up[i][0][1] == 0 && i != root2) up[i][0][1] = i;
    }
    for (int j=1;j<LOG;j++){
         for (int i=0;i<=maxNodeIndex;i++){
              int mid0 = up[i][j-1][0];
              up[i][j][0] = up[mid0][j-1][0];
              int mid1 = up[i][j-1][1];
              up[i][j][1] = up[mid1][j-1][1];
         }
    }

    tour = 0;
    dfs(root1,0);
    tour1 = tour;
    tour = 0;
    dfs(root2,1);
    tour2 = tour;

    pos.assign(tour2 + 2, vector<node>());

    res.assign(q, 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=LOG-1;j>=0;j--){
              int nx = up[x][j][1];
              if (nx >= 0 && val[nx][1] >= l){
                  x = nx;
              }
         }
         for (int j=LOG-1;j>=0;j--){
              int ny = up[y][j][0];
              if (ny >= 0 && val[ny][0] <= r){
                  y = ny;
              }
         }
         int idx_add = sta[x][1] - 1;
         int idx_rem = fin[x][1];
         int Lpos = sta[y][0];
         int Rpos = fin[y][0];
         if (idx_add >= 0 && idx_add <= tour2) pos[idx_add].push_back({Lpos,Rpos,-1,i});
         if (idx_rem >= 0 && idx_rem <= tour2) pos[idx_rem].push_back({Lpos,Rpos,1,i});
    }

    BITN = max(1, tour1 + 2);
    bit.assign(BITN+5, 0);

    for (int i=0;i<=tour2;i++){
         if (i){
             int node = rev[i][1];
             if (node >= 0 && node < (int)sta.size()){
                 int pos0 = sta[node][0];
                 if (pos0 > 0 && pos0 <= tour1) update(pos0-1, 1); 
                 else if (pos0 >= 0 && pos0 <= tour1) update(pos0, 1);
             }
         }
         for (auto &p:pos[i]){
              int cnt = query(p.r) - query(p.l-1);
              res[p.id]+= p.base * cnt;
         }
    }

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

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