Submission #1014975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014975		hyakup	Werewolf (IOI18_werewolf)	C++17	100 / 100	641 ms	150544 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define pii pair<int, int>

const int maxn = 2e5 + 10;
const int logn = 20;

int rep[maxn], tin[maxn], tout[maxn], pai[2][logn][maxn], sub[maxn], tempo;
vector<int> resp, adj[2][maxn];
vector<pii> queries[maxn];
set<int> s[maxn];

int find( int a ){ return (( a == rep[a] ) ? a : rep[a] = find(rep[a]) ); }
void join( int a, int b, int t ){
  a = find(a); b = find(b);
  if( a == b ) return;
  if( (a > b) == (bool)t ) swap( a, b );
  rep[b] = a;
  // cout << b << " -> " << a << endl;
  adj[t][a].push_back(b);
}

void dfsInit( int cur, int anc, int t ){
  if( t ) tin[cur] = ++tempo;
  pai[t][0][cur] = anc;
  for( int i = 1; i < logn; i++ ) pai[t][i][cur] = pai[t][i - 1][pai[t][i - 1][cur]];
  for( int viz : adj[t][cur] ) dfsInit( viz, cur, t );
  if( t ) tout[cur] = tempo;
}

int binary_lift1( int a, int l ){
  for( int i = logn - 1; i >= 0; i-- ) if( pai[1][i][a] >= l ) a = pai[1][i][a];
  return a;
}

int binary_lift2( int a, int r ){
  for( int i = logn - 1; i >= 0; i-- ) if( pai[0][i][a] <= r ) a = pai[0][i][a];
  return a;
}

void dfs( int cur, int pai ){
  // bug(cur);
  sub[cur] = 1;
  for( int& viz : adj[0][cur] ){
    dfs( viz, cur );
    sub[cur] += sub[viz];
    if( sub[viz] > sub[adj[0][cur][0]] ) swap( viz, adj[0][cur][0] );
  }
  if( adj[0][cur].empty() ){
    s[cur].insert(tin[cur]);
    for( auto [id, x] : queries[cur] ){
      auto it = s[cur].lower_bound(tin[x]);
      if( it != s[cur].end() && *it <= tout[x] ) resp[id] = 1;
    }
    return;
  }
  swap( s[cur], s[adj[0][cur][0]] );
  s[cur].insert(tin[cur]);
  for( int viz : adj[0][cur] ) if( viz != adj[0][cur][0] ) for( auto x : s[viz] ) s[cur].insert(x);

  for( auto [id, x] : queries[cur] ){
    auto it = s[cur].lower_bound(tin[x]);
    if( it != s[cur].end() && *it <= tout[x] ) resp[id] = 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 ){
  int n = N, m = (int)X.size(), q = (int)L.size();
  // bug(n); bug(m); bug(q);
  resp.resize(q);
  vector<pii> edges(m);
  for( int i = 0; i < m; i++ ) edges[i] = pii(min(X[i], Y[i]), max(X[i], Y[i]) );

  // arvore inicial - humano
  sort( edges.begin(), edges.end(), [&]( pii a, pii b ){
    return a.first > b.first;
  });
  for( int i = 0; i < n; i++ ) rep[i] = i;
  for( auto [a, b] : edges ) join( a, b, 1 );
  dfsInit( 0, 0, 1 );

  // cout << endl << endl;

  // arvore final - lobisomem
  sort( edges.begin(), edges.end(), [&]( pii a, pii b ){
    return a.second < b.second;
  });
  for( int i = 0; i < n; i++ ) rep[i] = i;
  for( auto [a, b] : edges ) join( a, b, 0 );
  dfsInit( n - 1, n - 1, 0 );

  // responde
  for( int i = 0; i < q; i++ ){
    int p1 = binary_lift1( S[i], L[i] ), p2 = binary_lift2( E[i], R[i] );
    // bug(p1);
    // bug(p2);
    queries[p2].push_back({ i, p1 });
  }

  dfs(n - 1, n - 1);
  // for( int i = 0; i < q; i++ ) cout << resp[i] << " ";
  return resp;
}

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