oj.uz

Submission #124736

# Submission time Handle Problem Language Result Execution time Memory
124736 2019-07-03T20:06:20 Z dragonslayerit Werewolf (IOI18_werewolf) C++14
100 / 100
 1295 ms 82272 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 9 ms 1400 KB Output is correct
11 Correct 9 ms 1400 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 9 ms 1400 KB Output is correct
14 Correct 8 ms 1400 KB Output is correct
15 Correct 9 ms 1432 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 82272 KB Output is correct
2 Correct 619 ms 66316 KB Output is correct
3 Correct 614 ms 64016 KB Output is correct
4 Correct 736 ms 63888 KB Output is correct
5 Correct 868 ms 64072 KB Output is correct
6 Correct 1002 ms 68496 KB Output is correct
7 Correct 923 ms 79676 KB Output is correct
8 Correct 583 ms 66372 KB Output is correct
9 Correct 575 ms 64084 KB Output is correct
10 Correct 635 ms 63384 KB Output is correct
11 Correct 698 ms 63968 KB Output is correct
12 Correct 739 ms 66604 KB Output is correct
13 Correct 634 ms 69364 KB Output is correct
14 Correct 603 ms 69496 KB Output is correct
15 Correct 584 ms 69400 KB Output is correct
16 Correct 569 ms 69348 KB Output is correct
17 Correct 1129 ms 79308 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 9 ms 1400 KB Output is correct
11 Correct 9 ms 1400 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 9 ms 1400 KB Output is correct
14 Correct 8 ms 1400 KB Output is correct
15 Correct 9 ms 1432 KB Output is correct
16 Correct 1295 ms 82272 KB Output is correct
17 Correct 619 ms 66316 KB Output is correct
18 Correct 614 ms 64016 KB Output is correct
19 Correct 736 ms 63888 KB Output is correct
20 Correct 868 ms 64072 KB Output is correct
21 Correct 1002 ms 68496 KB Output is correct
22 Correct 923 ms 79676 KB Output is correct
23 Correct 583 ms 66372 KB Output is correct
24 Correct 575 ms 64084 KB Output is correct
25 Correct 635 ms 63384 KB Output is correct
26 Correct 698 ms 63968 KB Output is correct
27 Correct 739 ms 66604 KB Output is correct
28 Correct 634 ms 69364 KB Output is correct
29 Correct 603 ms 69496 KB Output is correct
30 Correct 584 ms 69400 KB Output is correct
31 Correct 569 ms 69348 KB Output is correct
32 Correct 1129 ms 79308 KB Output is correct
33 Correct 947 ms 74336 KB Output is correct
34 Correct 320 ms 32472 KB Output is correct
35 Correct 806 ms 72440 KB Output is correct
36 Correct 957 ms 75432 KB Output is correct
37 Correct 971 ms 72620 KB Output is correct
38 Correct 934 ms 74748 KB Output is correct
39 Correct 820 ms 74888 KB Output is correct
40 Correct 818 ms 74680 KB Output is correct
41 Correct 723 ms 70132 KB Output is correct
42 Correct 708 ms 71436 KB Output is correct
43 Correct 778 ms 72592 KB Output is correct
44 Correct 802 ms 71184 KB Output is correct
45 Correct 703 ms 75912 KB Output is correct
46 Correct 762 ms 75788 KB Output is correct
47 Correct 633 ms 69684 KB Output is correct
48 Correct 564 ms 69460 KB Output is correct
49 Correct 564 ms 69644 KB Output is correct
50 Correct 563 ms 69384 KB Output is correct
51 Correct 766 ms 74016 KB Output is correct
52 Correct 737 ms 74140 KB Output is correct