Submission #1111634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111634		SalihSahin	Werewolf (IOI18_werewolf)	C++14	15 / 100	4065 ms	48920 KiB

werewolf

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "werewolf.h"
 
vector<int> par;
vector<vector<int> > adj1, adj2, adj;
 
int fnd(int a){
  if(a == par[a]) return a;
  return par[a] = fnd(par[a]);
}
 
bool merge(int a, int b, int g){
  a = fnd(a), b = fnd(b);
  if(a == b) return 0;
 
  if(g == 0){
    adj1[a].pb(b);
    adj1[b].pb(a);
    par[min(a, b)] = max(a, b);
  }
  else{
    adj2[a].pb(b);
    adj2[b].pb(a);
    par[max(a, b)] = min(a, b);
  }
 
  return 1;
}
 
vector<int> in1, out1, in2, out2, p1, p2;
int timer;
 
void dfs1(int node, int par){
  in1[node] = ++timer;
  p1[node] = par;
  for(auto itr: adj1[node]){
    if(itr == par) continue;
    dfs1(itr, node);
  }
  out1[node] = timer;
}
 
void dfs2(int node, int par){
  in2[node] = ++timer;
  p2[node] = par;
  for(auto itr: adj2[node]){
    if(itr == par) continue;
    dfs2(itr, node);
  }
  out2[node] = timer;
}
 
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();
  int m = X.size();
  adj1.resize(N);
  adj2.resize(N);
  adj.resize(N);
  par.resize(N);
  in1.resize(N);
  in2.resize(N);
  out1.resize(N);
  out2.resize(N);
  p1.resize(N);
  p2.resize(N);
 
  for(int i = 0; i < m; i++){
    adj[X[i]].pb(Y[i]);
    adj[Y[i]].pb(X[i]);
  }
  for(int i = 0; i < N; i++){
    par[i] = i;
  }
 
  for(int i = 0; i < N; i++){
    for(auto itr: adj[i]){
      if(itr > i) continue;
      merge(i, itr, 0);
    }
  } // adj1'i oluşturuyoruz -> werewolf path
 
  for(int i = 0; i < N; i++){
    par[i] = i;
  }
 
  for(int i = N-1; i >= 0; i--){
    for(auto itr: adj[i]){
      if(itr < i) continue;
      merge(i, itr, 1);
    }
  } // adj2'yi oluşturuyoruz -> human path
  timer = 0;
  dfs1(N-1, N-1);
  timer = 0;
  dfs2(0, 0);
  /*
  for(int i = 0; i < N; i++){
    cout<<i<<" -> "<<in1[i]<<" "<<out1[i]<<" ve 2. agac "<<in2[i]<<" "<<out2[i]<<endl;
  }*/
 
  vector<int> ans(q);
  for (int i = 0; i < q; ++i) {
    int start = S[i], finish = E[i];
    while(start != 0 && p2[start] >= L[i]) start = p2[start];
    while(finish != N-1 && p1[finish] <= R[i]) finish = p1[finish];
    //cout<<i<<" "<<start<<" "<<finish<<endl;
 
    bool ortak = 0;
    for(int j = L[i]; j <= R[i]; j++){
      bool anc2 = (in2[start] <= in2[j] && out2[start] >= out2[j]);
      bool anc1 = (in1[finish] <= in1[j] && out1[finish] >= out1[j]);
      if(anc1 && anc2){
        ortak = true;
        //cout<<i<<" -> "<<j<<" ok "<<endl;
      }
    }
 
    if(ortak) ans[i] = 1;
  }
  return ans;
}

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