Submission #1111633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111633		SalihSahin	Werewolf (IOI18_werewolf)	C++14	Compilation error	0 ms	0 KiB

werewolf

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "werewolf.h"

namespace {

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;
}

Compilation message (stderr)

werewolf.cpp:125:1: error: expected '}' at end of input
  125 | }
      | ^
werewolf.cpp:6:11: note: to match this '{'
    6 | namespace {
      |           ^
werewolf.cpp:57:13: warning: 'std::vector<int> {anonymous}::check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)' defined but not used [-Wunused-function]
   57 | vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
      |             ^~~~~~~~~~~~~~