Submission #1244617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244617		emad234	ICC (CEOI16_icc)	C++20	90 / 100	89 ms	648 KiB

icc

#include "icc.h"
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
int dsu[111];
vector<int> dset[111];
set<int>rts;
int find(int x){return(dsu[x] == x ? x : dsu[x] = find(dsu[x]));}
int CNT = 0;
void merge(int a,int b){
  int fa = find(a),fb = find(b);
  if(dset[fb].size() > dset[fa].size()) swap(fa,fb);
  for(auto x : dset[fb]) dset[fa].push_back(x);
  rts.erase(fb);
  dsu[fb] = fa;
}
vector<vector<int>> split(vector<int>f,vector<int>s){
  // if(CNT == 40) exit(0);
  vector<int>f1 = {},s1 = {};
  int szf = f.size(),szs = s.size();
  while(f.size() > f1.size()){
    int prev = -1;
    while(f.size() && (prev == -1 || find(f.back()) == prev)){
      prev = find(f.back());
      f1.push_back(f.back());
      f.pop_back();
      szf--;
    }
  }
  while(s.size() > s1.size()){
    int prev = -1;
    while(s.size() && (prev == -1 || find(s.back()) == prev)){
      prev = find(s.back());
      s1.push_back(s.back());
      s.pop_back();
    }
  }
  if(!f.size()){
    int prev = -1;
    while(f1.size() && (prev == -1 || find(f1.back()) == prev)){
      prev = find(f1.back());
      f.push_back(f1.back());
      f1.pop_back();
    }
  }
  if(!s.size()){
    int prev = -1;
    while(s1.size() && (prev == -1 || find(s1.back()) == prev)){
      prev = find(s1.back());
      s.push_back(s1.back());
      s1.pop_back();
    }
  }
  if(rand() % 2) swap(f1,s);
  else swap(f,s1);
  // cout<<"SPLIT OPERATION\n";
  // cout<<"F: ";
  // for(auto x : f) cout<<x<<' ';
  // cout<<'\n';
  // cout<<"S: ";
  // for(auto x : s) cout<<x<<' ';
  // cout<<'\n';
  // cout<<"F1: ";
  // for(auto x : f1) cout<<x<<' ';
  // cout<<'\n';
  // cout<<"S1: ";
  // for(auto x : s1) cout<<x<<' ';
  // cout<<'\n';
  // if(f1.size() + f.size() + s.size() + s1.size() == 0) exit(0);
  // CNT++;
  return {f,f1,s,s1};
}
int F[111],S[111];
vector<vector<int>>f,s;
bool spl = 1;
bool qmap(){
  // if(spl) cout<<"SPLIT\n";
  // else cout<<"FIND\n";
  int fsz = 0,ssz = 0;
  int i = 0,id = 0;
  // cout<<"F: ";
  while(id < f.size()){
    for(auto x : f[id]){
      F[i] = x;
      // cout<<F[i]<<' ';
      i++;
    }
    fsz += f[id].size();
    id++;
  }
  // cout<<'\n';
  i = 0;
  id = 0;
  // cout<<"S: ";
  while(id < s.size()){
    for(auto x : s[id]){
      S[i] = x;
      // cout<<S[i]<<' ';
      i++;
    }
    ssz += s[id].size();
    id++;
  }
  // cout<<'\n';
  return query(fsz,ssz,F,S);
}
bool cmp(int a,int b){
  return find(a) < find(b);
}
void run(int N){
  for(int i = 1;i <= N;i++){
    rts.insert(i);
    dsu[i] = i;
    dset[i] = {i};
  }
  int test = N - 1;
  while(test--){
    spl = 1;
    f.clear();
    s.clear();
    f.push_back({});
    s.push_back({});
    for(auto x : rts){
      for(auto el : dset[x]){
        f[0].push_back(el);
      }
    }
    // for(auto x : f[0]) cout<<x<<' ';
    while(f[0].size() > s[0].size()){
      int prev = -1;
      while(f[0].size() && (prev == -1 || find(f[0].back()) == prev)){
        prev = find(f[0].back());
        s[0].push_back(f[0].back());
        f[0].pop_back();
      }
    }
    // cout<<"INITSPLIT\n";
    // cout<<"F: ";
    // for(auto x : f[0]) cout<<x<<' ';
    // cout<<'\n';
    // cout<<"S: ";
    // for(auto x : s[0]) cout<<x<<' ';
    // cout<<'\n';
    bool found = qmap();
    while(!found){
      vector<vector<int>>ft,st;
      for(int i = 0;i < f.size();i++){
        auto x = split(f[i],s[i]);
        ft.push_back(x[0]);
        ft.push_back(x[1]);
        st.push_back(x[2]);
        st.push_back(x[3]);
      }
      f.clear();
      s.clear();
      for(auto x : ft){
        f.push_back(x);
      }
      for(auto x : st){
        s.push_back(x);
      }
      // cout<<f.size();
      // for(auto x : f){
      //   for(auto el : x) cout<<el<<' ';
      // }
      // cout<<'\n';
      found = qmap();
    }
    spl = 0;
    for(int i = 1;i < f.size();i++){
      for(auto x : f[i]) f[0].push_back(x);
      for(auto x : s[i]) s[0].push_back(x);
      f[i].clear();
      s[i].clear();
    }
    while(f[0].size() > 1){
      vector<int>fh,sh;
      for(int i = 0;i <f[0].size();i++){
        if(i < f[0].size() / 2) fh.push_back(f[0][i]);
        else sh.push_back(f[0][i]);
      }
      swap(fh,f[0]);
      found = qmap();
      if(!found) swap(sh,f[0]);
    }
    while(s[0].size() > 1){
      vector<int>fh,sh;
      for(int i = 0;i < s[0].size();i++){
        if(i < s[0].size() / 2) fh.push_back(s[0][i]);
        else sh.push_back(s[0][i]);
      }
      swap(fh,s[0]);
      found = qmap();
      if(!found) swap(sh,s[0]);
    }
    merge(f[0][0],s[0][0]);
    // cout<<"FOUND: "<<f[0][0]<<' '<<s[0][0]<<'\n';
    setRoad(f[0][0],s[0][0]);
  }

}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 0 / 10