Submission #1245683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245683		matisito	Werewolf (IOI18_werewolf)	C++20	34 / 100	758 ms	26588 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";


struct segtree{
  int n;
  vector<int>stmaxi, stmini;
  segtree(int n):n(n), stmaxi(2*n), stmini(2*n){}
  void update(int posi, int val){
    posi+=n;
    for(stmaxi[posi]=val, stmini[posi]=val ; posi>1 ; posi/=2){
      stmaxi[posi/2]=max(stmaxi[posi], stmaxi[posi^1]);
      stmini[posi/2]=min(stmini[posi], stmini[posi^1]);
    }
  }

  int qmax(int l, int r){
    r++;
    int res=0;
    for(l+=n, r+=n ; l<r ; l/=2, r/=2){
      if(l&1) res=max(res, stmaxi[l++]);
      if(r&1) res=max(res, stmaxi[--r]);
    }
    return res;
  }
  
  int qmin(int l, int r){
    r++;
    int res=1e9;
    for(l+=n, r+=n ; l<r ; l/=2, r/=2){
      if(l&1) res=min(res, stmini[l++]);
      if(r&1) res=min(res, stmini[--r]);
    }
    return res;
  }
};

vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  vector<vector<int>>g(N);
  for(int i=0 ; i<(int)X.size() ; i++){
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  int start;
  for(int i=0 ; i<N ; i++){
    if((int)g[i].size()==1){
      start=i;
      break;
    }
  }
  // dbg(start)
  queue<int>bfs;
  bfs.push(start);
  vector<int>vn, position(N);
  segtree st(N+5);
  vn.push_back(-1);
  vn.push_back(start);
  st.update(1, start);
  position[start]=1;
  vector<bool>vis(N);
  vis[start]=1;
  while(!bfs.empty()){
    int u=bfs.front();
    bfs.pop();
    for(int v:g[u]){
      if(!vis[v]){
        vis[v]=1;
        bfs.push(v);
        vn.push_back(v);
        // dbg(v)
        // dbg((int)vn.size()-1);
        st.update((int)vn.size()-1, v);
        position[v]=(int)vn.size()-1;
      }
    }
  }
  // for(int i=0 ; i<N ; i++) dbg(position[i])
  vector<int>ans((int)L.size());
  for(int i=0 ; i<(int)L.size() ; i++){
    // dbg(position[S[i]])
    // dbg(position[E[i]])
    if(position[S[i]]<=position[E[i]]){
      int valenotta=position[S[i]], matijim=position[E[i]];
      int l=position[S[i]], r=position[E[i]];
      while(l<=r){
        int mid=(l+r)/2;
        // dbg(mid)
        // dbg(position[S[i]])
        // dbg(st.qmin(position[S[i]], mid))
        if(st.qmin(position[S[i]], mid)<L[i]) r=mid-1;
        else{
          valenotta=mid;
          l=mid+1;
        }
      }
      l=position[S[i]], r=position[E[i]];
      while(l<=r){
        int mid=(l+r)/2;
        if(st.qmax(mid, position[E[i]])>R[i]) l=mid+1;
        else{
          matijim=mid;
          r=mid-1;
        }
      }
      // dbg(valenotta)
      // dbg(matijim)
      if(matijim<=valenotta) ans[i]=1;
      else ans[i]=0;
    }else{
      int valenotta=position[S[i]], matijim=position[E[i]];
      int r=position[S[i]], l=position[E[i]];
      while(l<=r){
        int mid=(l+r)/2;
        if(st.qmin(mid, position[S[i]])<L[i]) l=mid+1;
        else{
          valenotta=mid;
          r=mid-1;
        }
      }
      r=position[S[i]], l=position[E[i]];
      while(l<=r){
        int mid=(l+r)/2;
        if(st.qmax(position[E[i]], mid)>R[i]) r=mid-1;
        else{
          matijim=mid;
          l=mid+1;
        }
      }
      if(matijim>=valenotta) ans[i]=1;
      else ans[i]=0;
    }
  }
  return ans;
}

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