Submission #262020

#	Time	Username	Problem	Language	Result	Execution time	Memory
262020		youssefbou62	Werewolf (IOI18_werewolf)	C++14	0 / 100	481 ms	36072 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

#define sz(x)	(int)x.size()
#define pb push_back 
#define fi first 
#define se second 
#define pi pair<int,int> 
#define all(x) x.begin(),x.end() 
using namespace std; 

const int MAXN = 2e5+5 ; 
bool visited0[MAXN];
int cnt , g_left[MAXN],g_right[MAXN],par[MAXN],pos[MAXN]; 
pi start_int[MAXN],end_int[MAXN]; 
vector<int> adj[MAXN] ; 


void dfs0(int u){

	visited0[u] = 1 ; 
  pos[u] = cnt ; 
  par[u] = u ;  
  cnt ++ ; 
	for(int v : adj[u]){
		if( !visited0[v] ){
			dfs0(v); 
		}
	}
}

int fs(int u){
  if( u == par[u] )return u ; 
  return par[u]=fs(par[u]) ;
}


void us(int u,int v){
  u = fs(u) ; 
  v = fs(v) ; 
  if( u == v )return ; 
  par[v] = u ; 
  g_left[u] = min(g_left[u],g_left[v]); 
  g_right[u] = max(g_right[u],g_right[v]);

}

bool intersect(pi a,pi b){
  return max(a.fi,b.fi)<=min(a.se,b.se); 
}
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 = sz(X); 
  vector<pair<int,int>> queries ; 
  int Q = sz(L); 
  vector<int> A(Q); 
	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++ ){
    if( sz(adj[i])==1 ){
      dfs0(i) ;
      break ;  
    }
  }
  // cerr <<"****"<<endl; 
  // for(int i = 0 ; i < N ; i++ ){
  //   cout << i << " " << g_left[i] << " " << g_right[i]<<endl; 
  // }
  // cerr <<"******"<<endl; 
  for(int i = 0 ; i < Q ; i++ ){
    queries.pb({L[i],i}); 
  }
  sort(all(queries)); 
  memset(g_left,-1,sizeof g_left); 
  memset(g_right,-1,sizeof g_right); 
  for(int i = N-1 , j = Q-1; i != -1 ; i-- ){

      g_left[i] = pos[i] ; 
      g_right[i] = pos[i] ;
      for(int v : adj[i]){
        if(v>=i)
          us(v,i); 
      }

      while (j!=-1&&queries[j].fi == i ){
        int x = queries[j].se ; 
        // cerr <<"ye " << S[x] << " " << fs(S[x])<< endl; 
        start_int[x] = {g_left[fs(S[x])],g_right[fs(S[x])]}; 
        j--; 
      }

  }
  for(int i = 0 ; i < Q ; i++ ){
    queries[i].fi=R[i]; 
  }
  sort(all(queries)) ;
  memset(visited0,0,sizeof visited0);
  memset(g_left,-1,sizeof g_left); 
  memset(g_right,-1,sizeof g_right); 
  for(int i = 0 ; i < N ; i++ )par[i] = i  ;
  for(int i = 0 , j = 0 ; i < N ; i++ ){
      g_left[i] = pos[i] ; 
      g_right[i] = pos[i] ;
    for(int v : adj[i]){
      if( v <= i )
        us(v,i); 
    }

    while (j<Q&&queries[j].fi==i){
      int x = queries[j].se ; 
        end_int[x] = {g_left[fs(E[x])],g_right[fs(E[x])]}; 
        j++; 
    }
  }
  for(int i = 0 ; i < Q ; i++ ){
    // cerr <<"query n "<<i<<"******"; 
    // cerr << "start int "<< start_int[i].fi << " " << start_int[i].se <<endl; 
    // cerr << "end int "<< end_int[i].fi << " " << end_int[i].se <<endl; 
    
    A[i] = intersect(start_int[i],end_int[i]) ; 
  }

  return A;
}


// namespace {

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// }  // namespace

// int main() {
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int()-1;
//     Y[j] = read_int()-1;
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int()-1;
//     E[i] = read_int()-1;
//     L[i] = read_int()-1;
//     R[i] = read_int()-1;
//   }

//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d\n", A[i]);
//   }
//   return 0;
// }

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