제출 #58586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58586		ruhanhabib39	ICC (CEOI16_icc)	C++17	0 / 100	400 ms	780 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

// query(|A|,|B|,A,B) (A, B) disjoint, returns whether there's an edge between A, B
// setRoad(u,v) tells there's an edge u--v

namespace {
   int par[100 + 10];
   vector<int> st[100 + 10];
   vector<int> sts;
   int N;
   void init(int N_) {
      N = N_; sts.reserve(N);
      for(int i = 1; i <= N; i++) {
         par[i] = i;
         st[i].push_back(i);
         sts.push_back(i);
      }
   }
   int find(int u) {
      if(par[u] == u) return u;
      return par[u] = find(par[u]);
   }
   void merge(int u, int v) {
      u = find(u); v = find(v);
      if(u == v) return;
      if(st[v].size() > st[u].size()) {
         swap(v, u);
      }
      par[v] = u;
      st[u].insert(st[u].end(), st[v].begin(), st[v].end());
      sort(st[u].begin(), st[u].end());
      st[u].resize(unique(st[u].begin(), st[u].end()) - st[u].begin());
      sts.erase(find(sts.begin(), sts.end(), v));
      cerr << "merge(" << u << ", " << v << ")\n";
   }
   vector<int> build(int l, int r) {
      vector<int> rs;
      for(int i = l; i <= r; i++) {
         rs.insert(rs.end(), st[sts[i]].begin(), st[sts[i]].end());
      }
      return rs;
   }
   vector<int> get(vector<int> v, int l, int r) {
      vector<int> rs(v.begin() + l, v.begin() + r + 1);
      return rs;
   }
   bool hasEdge(int al, int ar, int bl, int br) {
      auto A = build(al, ar); auto B = build(bl, br);
      bool rs = query(A.size(), B.size(), A.data(), B.data());
      return rs;
   }
   void superPinPoint(int u, int v) {
      //cerr << "superPinPoint(" << u << ", " << v << ")\n";
      auto A = st[u]; auto B = st[v];
      while(A.size() > 1) {
         //cerr << "|A| = " << A.size() << "\n";
         int m = (A.size() - 1)/ 2;
         //cerr << "m = " << m << "\n";
         auto AA = get(A, 0, m);
         //cerr << "|AA| = " << AA.size() << "\n";
         if(query(AA.size(), B.size(), AA.data(), B.data())) A = AA;
         else A = get(A, m+1, A.size()-1);
      }
      while(B.size() > 1) {
         int m = (B.size() - 1) / 2;
         auto BB = get(B, 0, m);
         if(query(A.size(), BB.size(), A.data(), BB.data())) B = BB;
         else B = get(B, m+1, B.size()-1);
      }
      setRoad(A[0], B[0]);
   }
   void pinpointEdge(int l0, int r0, int l1, int r1) {
      //cerr << "pinpointing\n";
      //cerr << "[" << l0 << ", " << r0 << "]\n";
      while(l0 < r0) {
         //cerr << "left[" << l0 << ", " << r0 << "]\n";
         int m = (l0 + r0) / 2;
         if(hasEdge(l0,m,l1,r1)) r0 = m;
         else l0 = m + 1;
      }
      while(l1 < r1) {
         int m = (l1 + r1) / 2;
         if(hasEdge(l0,r0,l1,m)) r1 = m;
         else l1 = m + 1;
      }
      int u = sts[l0], v = sts[l1];
      superPinPoint(u, v);
      merge(u, v);
   }
   bool findEdge(int l, int r) {
      if(l >= r) return false;
      int m = (l + r) / 2;
      if(hasEdge(l,m,m+1, r)) {
         pinpointEdge(l, m, m+1, r);
         return true;
      }
      return findEdge(l, m) or findEdge(m+1, r);
   }
};

void run(int n) {
   init(n);
   for(int i = 0; i < n-1; i++) {
      findEdge(0,sts.size()-1);
   }
}

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