제출 #1244833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244833		repmann	ICC (CEOI16_icc)	C++20	90 / 100	1716 ms	636 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
bool D[101], VG[101][101];
struct NODE
{
  int parent, num;
  vector <int> V;
}DSU[101];
//inline bool query(int size_a, int size_b, int a[], int b[])
//{
//  cout << "Query:\n";
//  cout << size_a << '\n';
//  for(int i = 0; i < size_a; i++) cout << a[i] << " \n"[i == (size_a - 1)];
//  cout << size_b << '\n';
//  for(int i = 0; i < size_b; i++) cout << b[i] << " \n"[i == (size_b - 1)];
//  bool ans;
//  cin >> ans;
//  return ans;
//}
//inline void setRoad(int u, int v)
//{
//  cout << "Set: " << u << ' ' << v << '\n';
//  return;
//}
inline int Find(int u)
{
  if(u != DSU[u].parent) return Find(DSU[u].parent);
  return u;
}
inline void Union(int u, int v)
{
  u = Find(u);
  v = Find(v);
  if(u == v) return;
  if(DSU[u].num < DSU[v].num) swap(u, v);
  DSU[v].parent = u;
  DSU[u].num += DSU[v].num;
  for(int x : DSU[v].V) DSU[u].V.push_back(x);
  DSU[v].V = vector <int>();
  return;
}
inline int Component(int size_a, int size_b, int a[], int b[])
{
  int L = 0, R = size_a - 1, S, temp[size_a];
  while(L < R)
  {
    S = (L + R) >> 1;
    for(int i = L, j = 0; i <= S; i++) temp[j++] = a[i];
    if(!query(S - L + 1, size_b, temp, b)) L = S + 1;
    else R = S;
  }
  return a[R];
}
inline int BS(int size_a, int size_b, int a[], int b[])
{
  vector <int> V;
  memset(D, 0, sizeof(D));
  for(int i = 0; i < size_a; i++) D[Find(a[i])] = 1;
  for(int i = 1; i <= 100; i++) if(D[i]) V.push_back(i);
  int L = 0, R = V.size() - 1, S, temp[size_a];
  while(L < R)
  {
    S = (L + R) >> 1;
    int num = 0;
    for(int i = L, j = 0; i <= S; i++)
    {
      num += DSU[V[i]].num;
      for(int x : DSU[V[i]].V) temp[j++] = x;
    }
    if(!query(num, size_b, temp, b)) L = S + 1;
    else R = S;
  }
  for(int i = 0, j = 0; i < DSU[V[R]].V.size(); i++) temp[j++] = DSU[V[R]].V[i];
  return Component(DSU[V[R]].num, size_b, temp, b);
}
void run(int N)
{
  for(int i = 1; i <= N; i++) DSU[i] = {i, 1, {i}};
  int edges = N - 1;
  while(edges--)
  {
    int num, u, v, a[N], b[N];
    memset(VG, 0, sizeof(VG));
    do
    {
      int iterations = 300, temp, prev = 0, best = 0;
      memset(D, 0, sizeof(D));
      vector <int> V, VCPY;
      for(int i = 1, j; i <= N; i++)
      {
        j = Find(i);
        if(D[j]) continue;
        D[j] = true;
        V.push_back(j);
      }
      while(iterations--)
      {
        random_shuffle(V.begin(), V.end());
        num = 0, temp = 0;
        for(int i = 0; i < V.size(); i++)
        {
          num += DSU[V[i]].num;
          for(int x : DSU[V[i]].V)
          {
            for(int j = 0; j < i; j++)
            {
              for(int y : DSU[V[j]].V) temp -= VG[x][y];
            }
            for(int j = i + 1; j < V.size(); j++)
            {
              for(int y : DSU[V[j]].V) temp += VG[x][y];
            }
          }
          if(((num * (N - num) - temp) < prev) && (num > (N >> 1))) break;
          prev = num * (N - num) - temp;
          if((num * (N - num) - temp) <= best) continue;
          best = num * (N - num) - temp;
          VCPY = vector <int>();
          for(int j = 0; j <= i; j++) VCPY.push_back(V[j]);
        }
      }
      for(int i = 0; i < VCPY.size(); i++)
      {
        for(int x : DSU[VCPY[i]].V)
        {
          for(int j = 0; j < V.size(); j++)
          {
            bool flag = false;
            for(int y : VCPY) if(V[j] == y) {flag = true; break;}
            if(flag) continue;
            for(int y : DSU[V[j]].V) VG[x][y] = VG[y][x] = 1;
          }
        }
      }
      memset(D, 0, sizeof(D));
      num = 0;
      for(int x : VCPY)
      {
        num += DSU[x].num;
        for(int y : DSU[x].V) D[y] = 1;
      }
      for(int i = 1, j = 0; i <= N; i++) if(D[i]) a[j++] = i;
      for(int i = 1, j = 0; i <= N; i++) if(!D[i]) b[j++] = i;
    }while(!query(num, N - num, a, b));
    a[0] = u = BS(num, N - num, a, b);
    v = BS(N - num, 1, b, a);
    Union(u, v);
    setRoad(u, v);
  }
  return;
}
//int main()
//{
//  int n;
//  cin >> n;
//  run(n);
//
//  return 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