Submission #124736

#	Time	Username	Problem	Language	Result	Execution time	Memory
124736		dragonslayerit	Werewolf (IOI18_werewolf)	C++14	100 / 100	1295 ms	82272 KiB

werewolf

#include "werewolf.h"
#include <map>
#include <iostream>

int find(std::vector<int>& uf,int a){
  return (a==uf[a])?a:(uf[a]=find(uf,uf[a]));
}

struct HLD{
  int N;
  std::vector<std::vector<int> > adj;
  std::vector<int> size,parent,head;
  HLD(int N):N(N),adj(N),size(N),parent(N,-1),head(N){
  }
  void add_edge(int A,int B){
    adj[A].push_back(B);
    parent[B]=A;
  }
  void dfs_size(int node){
    size[node]=1;
    for(int child:adj[node]){
      dfs_size(child);
      size[node]+=size[child];
    }
  }
  void dfs_hld(int node){
    for(int& child:adj[node]){
      if(size[child]>size[adj[node][0]]){
	std::swap(child,adj[node][0]);
      }
    }
    for(int child:adj[node]){
      //std::cerr<<"HLD: "<<node<<" "<<child<<std::endl;
      head[child]=(child==adj[node][0])?head[node]:child;
      dfs_hld(child);
    }
  }
  void build(){
    for(int i=0;i<N;i++){
      if(parent[i]==-1){
	dfs_size(i);
	dfs_hld(i);
      }
    }
  }
};

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<std::vector<int> > adj(N);
  for(int i=0;i<X.size();i++){
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  struct HLD stree(N),etree(N);
  {
    std::vector<int> uf(N);
    for(int i=0;i<N;i++){
      uf[i]=i;
    }
    std::vector<std::vector<int> > at(N);
    for(int i=0;i<Q;i++){
      at[R[i]].push_back(i);
    }
    for(int i=0;i<N;i++){
      for(int j:adj[i]){
	if(j<i){
	  j=find(uf,j);
	  if(i!=j){
	    etree.add_edge(i,j);
	    uf[j]=i;
	  }
	}
      }
      for(int j:at[i]){
	E[j]=find(uf,E[j]);
      }
    }
  }
  {
    std::vector<int> uf(N);
    for(int i=0;i<N;i++){
      uf[i]=i;
    }
    std::vector<std::vector<int> > at(N);
    for(int i=0;i<Q;i++){
      at[L[i]].push_back(i);
    }
    for(int i=N-1;i>=0;i--){
      for(int j:adj[i]){
	if(j>i){
	  j=find(uf,j);
	  if(i!=j){
	    stree.add_edge(i,j);
	    uf[j]=i;
	  }
	}
      }
      for(int j:at[i]){
	S[j]=find(uf,S[j]);
      }
    }
  }
  //std::cerr<<"STREE"<<std::endl;
  stree.build();
  //std::cerr<<"ETREE"<<std::endl;
  etree.build();
  
  std::vector<std::vector<int> > at(N);
  for(int i=0;i<Q;i++){
    at[E[i]].push_back(i);
    //std::cerr<<"Q: "<<S[i]<<" "<<E[i]<<std::endl;
  }
  std::vector<std::map<int,int>*> match(N);
  std::vector<int> A(Q);
  for(int i=0;i<N;i++){
    if(etree.adj[i].size()){
      match[i]=match[etree.adj[i][0]];
    }else{
      match[i]=new std::map<int,int>();
    }
    int v=i;
    while(true){
      int& x=(*match[i])[stree.head[v]];
      x=std::max(x,v);
      v=stree.head[v];
      if(stree.parent[v]==-1) break;
      v=stree.parent[v];
    }
    for(int j:etree.adj[i]){
      if(j!=etree.adj[i][0]){
	//insert match[j] into match[i]
	for(auto it:*match[j]){
	  int& x=(*match[i])[it.first];
	  x=std::max(x,it.second);
	}
	delete match[j];
      }
    }
    /*
    for(auto it:*match[i]){
      std::cerr<<"At "<<i<<": "<<"("<<it.first<<","<<it.second<<")"<<std::endl;
    }
    */
    for(int j:at[i]){
      A[j]=((*match[i])[stree.head[S[j]]]>=S[j]);
    }
  }
  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<X.size();i++){
               ~^~~~~~~~~

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