Submission #1267125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267125		ThylOne	Werewolf (IOI18_werewolf)	C++20	100 / 100	398 ms	101348 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;

struct unionFind{
    vector<int> chef, in, out;
    vector<vector<int>> links;
    int e = 0;
    
    int find(int x){
      if(chef[x] == x)return x;
      return chef[x] = find(chef[x]);
    }
    pair<int,int> getCompoConnexe(int x){
      assert(in[x] >0);
      assert(out[x]>0);

      return make_pair(in[x], out[x]);
    }
    //l'ordre compte tres fort ici
    void make_A_in_B(int a, int b){
      a = find(a);
      b = find(b);
      if(a != b){
        links[b].push_back(a);
        chef[a] = b;
      }
    }
    void dfs(int node){
      in[node] = ++e;
      for(int v:links[node])
        dfs(v);
      out[node] = ++e;
    }
    void computeEuleurTour(){
      e = 0;
      for(int i = 0 ; i < chef.size() ; i++){
        if(find(i) == i){
          dfs(i);
        }
      }
    }
    unionFind(int n){
      chef.resize(n);
      in.resize(n);
      out.resize(n);
      links.resize(n);

      for(int i=0;i<n;i++)chef[i]=i;
    }
};
struct req{
  int d,f,id;
};
struct Fenwick{
  vector<int> vals;
  Fenwick(int n){
    vals.resize(n+1,0);
  }
  #define LSONE(x) ((x)&(-x))
  void updatePoint(int pos, int v){
    while(pos < vals.size()){
      vals[pos] += v;
      pos += LSONE(pos);
    }
  }
  int get(int i){
    int re = 0;
    while(i){
      re += vals[i];
      i -= LSONE(i);
    }
      
    return re;
  }
  int get(int i, int j){
    return get(j) - get(i-1);
  }
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  //liste d'adjacence
  vector<int> links[N];
  for(int e = 0 ; e < X.size() ; e++){
    links[X[e]].push_back(Y[e]);
    links[Y[e]].push_back(X[e]);
  }


  int Q = S.size();
  vector<pair<int,int>> eventH[N], eventW[N];
  for(int i = 0 ; i < Q ; i++){
    eventH[L[i]].push_back({S[i], i});
    eventW[R[i]].push_back({E[i], i});
  }
  vector<int> queryS(Q), queryE(Q);
  
  unionFind ufW(N), ufH(N);
  for(int city = 0 ; city < N ; city++){
    for(int u:links[city])if(u < city){
      ufW.make_A_in_B(u, city);
    }
    //on garde en memoire le chef a ce moment city

    for(auto event:eventW[city]){
      queryE[event.second]  = ufW.find(event.first);
    }
  }
  for(int city = N - 1 ; city >= 0 ; city--){
    for(int u:links[city])if(u > city){
      ufH.make_A_in_B(u, city);
    }
    //on garde en memoire le chef a ce moment city
    for(auto event:eventH[city]){
      queryS[event.second]  = ufH.find(event.first);
    }
  }
  
  //conpute les euleurs tours
  ufH.computeEuleurTour();
  ufW.computeEuleurTour();

  const int W = 1 + 2*N;
  vector<int> addY[W];//les events pour ajouter les pts dans le fenwick
  vector<req> reqs[W];
  for(int i = 0 ; i < N ; i++){
    addY[ufH.in[i]].push_back(ufW.out[i]);
  }

  for(int r = 0 ; r < Q ; r++){
    auto humanP = ufH.getCompoConnexe(queryS[r]);
    auto werewolfP = ufW.getCompoConnexe(queryE[r]);
    //pour faire de l'inclusion exclusion
    reqs[humanP.first - 1].push_back({werewolfP.first, werewolfP.second, r});
    reqs[humanP.second   ].push_back({werewolfP.first, werewolfP.second, r});
  }
  

  vector<int> ans(Q,-1);
  Fenwick ft(W);
  for(int x = 0 ; x < W ; x++){
    //On met les points sur la D
    for(int y:addY[x])ft.updatePoint(y,  1);
    for(auto R:reqs[x]){
      if(ans[R.id] == -1){//prefix left
        ans[R.id] = ft.get(R.d, R.f);
      }else{//prefi right
        ans[R.id] = ft.get(R.d, R.f) - ans[R.id];
      }
    }
    
  }
  for(int &i:ans)if(i>0)i=1;

  return ans;
}

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