Submission #1238459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238459		noyancanturk	Werewolf (IOI18_werewolf)	C++20	0 / 100	350 ms	589824 KiB

werewolf

#include "werewolf.h"

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

#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

vector<int>v[lim];

int vis1[lim],vis2[lim];

vector<int>a;
int tr[lim];
vector<int>ans;

void dfs(int node,int par){
  a.pb(node);
  for(int j:v[node]){
    if(j==par)continue;
    dfs(j,node);
  }
}

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 m=X.size();
  int q=s.size();
  ans.resize(q);
  for(int i=0;i<m;i++){
    v[X[i]].pb(Y[i]);
    v[Y[i]].pb(X[i]);
  }
  for(int i=0;i<n;i++){
    if(v[i].size()==1){
      dfs(i,-1);
      break;
    }
  }
  for(int i=0;i<n;i++){
    tr[a[i]]=i;
  }
  auto solve=[&]() -> void {
    // cerr<<"beg solve\n";
    // for(int i=0;i<n;i++)cerr<<a[i]<<' ';
    // cerr<<'\n';
    // for(int i=0;i<n;i++){
    //   cerr<<tr[i]<<' ';
    // }
    // cerr<<'\n';
    vector<int>needansl[n],needansr[n];
    for(int i=0;i<n;i++){
      if(tr[s[i]]<tr[e[i]]){
        needansl[s[i]].pb(i);
        needansr[e[i]].pb(i);
      }
    }
    int cangol[q],cangor[q];
    for(int i=0;i<q;i++){
      cangol[i]=INT_MAX;
      cangor[i]=INT_MIN;
    }
    vector<int>st;
    for(int i=0;i<n;i++){
      while(st.size()&&a[st.back()]<a[i]){
        st.pop_back();
      }
      st.pb(i);
      for(int id:needansr[i]){
        int l=0,r=st.size()-1;
        cangol[id]=0;
        while(l<=r){
          int mid=l+r>>1;
          if(a[st[mid]]>R[id]){
            cangol[id]=st[mid]+1;
            l=mid+1;
          }else{
            r=mid-1;
          }
        }
      }
    }
    st.clear();
    for(int i=n-1;0<=i;i--){
      while(st.size()&&a[st.back()]>a[i]){
        st.pop_back();
      }
      st.pb(i);
      // cerr<<"deb :: ";
      // for(int i:st)cerr<<a[i]<<' ';
      // cerr<<'\n';
      for(int id:needansl[i]){
        int l=0,r=st.size()-1;
        cangor[id]=n-1;
        while(l<=r){
          int mid=l+r>>1;
          // if(id==3){
          //   cerr<<i<<' '<<a[st[mid]]<<' '<<L[id]<<" are ids\n";
          // }
          if(a[st[mid]]<L[id]){
            cangor[id]=st[mid]-1;
            l=mid+1;
          }else{
            r=mid-1;
          }
        }
      }
    }
    for(int i=0;i<q;i++){
      ans[i]|=cangol[i]<=cangor[i];
    }
    // cerr<<cangol[3]<<' '<<cangor[3]<<'\n';
  };
  // for(int i=0;i<n;i++){
  //   cerr<<a[i]<<' ';
  // }cerr<<'\n';
  solve();
  for(int i=0;i<n;i++){
    tr[i]=n-tr[i]-1;
  }
  // cerr<<a.size()<<'\n';
  // for(int i=0;i<n;i++){
  //   cerr<<a[i]<<' ';
  // }cerr<<'\n';
  reverse(a.begin(),a.end());
  // for(int i=0;i<n;i++){
  //   cerr<<a[i]<<' ';
  // }cerr<<'\n';
  solve();
  return ans;
}

// std::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) {
//   int Q = S.size();
//   std::vector<int> A(Q);
//   for (int i = 0; i < Q; ++i) {
//     A[i] = 0;
//   }
//   return A;
// }

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