oj.uz

Submission #135416

# Submission time Handle Problem Language Result Execution time Memory
135416 2019-07-24T05:07:51 Z dragonslayerit ICC (CEOI16_icc) C++14
61 / 100
 200 ms 632 KB 
#include "icc.h"

#include <vector>
#include <cassert>
#include <algorithm>

struct UnionFind{
  std::vector<int> uf;
  UnionFind(int N):uf(N){
    for(int i=0;i<N;i++){
      uf[i]=i;
    }
  }
  int find(int a){
    while(a!=uf[a]){
      a=uf[a]=uf[uf[a]];
    }
    return a;
  }
  void merge(int a,int b){
    uf[find(a)]=find(b);
  }
  int size(){
    return uf.size();
  }
  bool isRoot(int a){
    return a==uf[a];
  }
}uf(0);

bool query1(std::vector<int> a,std::vector<int> b){
  for(int& x:a) x++;
  for(int& x:b) x++;
  return query(a.size(),b.size(),a.data(),b.data());
}

template<class Iterator>
bool query1(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
  return query1(std::vector<int>(b1,e1),std::vector<int>(b2,e2));
}

template<class Iterator>
std::pair<int,int> locate1(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
  while(e1-b1>1){
    Iterator m1=b1+(e1-b1)/2;
    if(query1(b1,m1,b2,e2)){
      e1=m1;
    }else{
      b1=m1;
    }
  }
  while(e2-b2>1){
    Iterator m2=b2+(e2-b2)/2;
    if(query1(b1,e1,b2,m2)){
      e2=m2;
    }else{
      b2=m2;
    }
  }
  return std::pair<int,int>(*b1,*b2);
}

bool query2(std::vector<int> a,std::vector<int> b){
  std::vector<int> c,d;
  for(int i=0;i<uf.size();i++){
    if(std::find(a.begin(),a.end(),uf.find(i))!=a.end()){
      c.push_back(i+1);
    }
    if(std::find(b.begin(),b.end(),uf.find(i))!=b.end()){
      d.push_back(i+1);
    }
  }
  return query(c.size(),d.size(),c.data(),d.data());
}

template<class Iterator>
bool query2(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
  return query2(std::vector<int>(b1,e1),std::vector<int>(b2,e2));
}

template<class Iterator>
std::pair<int,int> locate2(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
  while(e1-b1>1){
    Iterator m1=b1+(e1-b1)/2;
    if(query2(b1,m1,b2,e2)){
      e1=m1;
    }else{
      b1=m1;
    }
  }
  while(e2-b2>1){
    Iterator m2=b2+(e2-b2)/2;
    if(query2(b1,e1,b2,m2)){
      e2=m2;
    }else{
      b2=m2;
    }
  }
  return std::pair<int,int>(*b1,*b2);
}

template<class Iterator>
std::pair<int,int> locate2(Iterator begin,Iterator end){
  for(int k=0;(1<<k)<end-begin;k++){
    std::vector<int> as,bs;
    for(int i=0;i<end-begin;i++){
      if(i&(1<<k)){
	as.push_back(*(begin+i));
      }else{
	bs.push_back(*(begin+i));
      }
    }
    if(query2(as,bs)){
      return locate2(as.begin(),as.end(),bs.begin(),bs.end());
    }
  }
  assert(0);
}

void solve(){
  std::vector<int> reps;
  for(int i=0;i<uf.size();i++){
    if(uf.isRoot(i)){
      reps.push_back(i);
    }
  }
  std::pair<int,int> pair=locate2(reps.begin(),reps.end());
  std::vector<int> as,bs;
  for(int i=0;i<uf.size();i++){
    if(uf.find(i)==uf.find(pair.first)){
      as.push_back(i);
    }
    if(uf.find(i)==uf.find(pair.second)){
      bs.push_back(i);
    }
  }
  pair=locate1(as.begin(),as.end(),bs.begin(),bs.end());
  setRoad(pair.first+1,pair.second+1);
  uf.merge(pair.first,pair.second);
}

void run(int N){
  uf=UnionFind(N);
  for(int i=0;i<N-1;i++){
    solve();
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 114 queries used.
2 Correct 9 ms 504 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 588 KB Ok! 660 queries used.
2 Correct 53 ms 476 KB Ok! 683 queries used.
3 Correct 54 ms 504 KB Ok! 716 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 560 KB Ok! 1836 queries used.
2 Correct 170 ms 604 KB Ok! 1618 queries used.
3 Correct 177 ms 508 KB Ok! 1937 queries used.
4 Correct 176 ms 572 KB Ok! 1833 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 560 KB Ok! 1905 queries used.
2 Correct 176 ms 504 KB Ok! 1889 queries used.
3 Correct 174 ms 560 KB Ok! 1892 queries used.
4 Correct 172 ms 504 KB Ok! 1874 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 632 KB Too many queries! 1877 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 556 KB Too many queries! 1844 out of 1625
2 Halted 0 ms 0 KB -