| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 24655 | bill_kondo | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 1e2 + 10;
const int maxC = 1e2 + 10;
int n;
set <pii> e;
int c[maxn];
int d[maxn];
void acha ()
{
for (int a = 1; a <= n; ++a)
for (int b = a + 1; b <= n; ++b)
if (e.find (pii (a, b)) == e.end())
{
c[0] = {a};
d[0] = {b};
if (query (1, 1, c, d))
{
e.insert (pii (a, b));
setRoad (a, b);
return;
}
}
}
int pointer;
vector <int> adj[maxn];
bool mrk[maxn];
int node, E[maxn], p;
void combina (int l, int r)
{
if (l == r)
{
node = d[l];
return;
}
int mid = (l + r) >> 1;
p = 0;
for (int i = l; i <= mid; ++i)
E[p++] = d[i];
if (query (1, p, c, E))
combina (l, mid);
else
combina (mid + 1, r);
}
void dfs (int v)
{
mrk[v] = true;
for (auto u: adj[v])
if (!mrk[u])
dfs (u);
}
void aresta ()
{
for (int v = 1; v <= n; ++v)
{
c[0] = v;
for (int u = 1; u <= n; ++u)
mrk[u] = false;
dfs (v);
pointer = 0;
for (int u = 1; u <= n; ++u)
if (!mrk[u])
d[pointer++] = u;
if (query (1, pointer, c, d))
{
combina (0, pointer - 1);
adj[v].push_back (node);
adj[node].push_back (v);
setRoad (v, node);
return;
}
}
}
vector <int> C[maxC];
void DFS (int v, int id)
{
mrk[v] = true;
C[id].push_back (v);
for (auto u: adj[v])
if (!mrk[u])
DFS (u, id);
}
int pA, A[maxn];
int pB, B[maxn];
int pC, C[maxn];
int I, J;
void combineA (int l, int r)
{
if (l == r)
{
I = l;
return;
}
int mid = (l + r) >> 1;
pC = 0;
for (int i = l; i <= mid; ++i)
C[pC++] = B[i];
if (query (pA, pC, A, C))
combineA (l, mid);
else
combineA (mid + 1, r);
}
void combineB (int l, int r)
{
if (l == r)
{
J = l;
return;
}
int mid = (l + r) >> 1;
pC = 0;
for (int i = l; i <= mid; ++i)
C[pC++] = A[i];
if (query (pB, pC, B, C))
combineB (l, mid);
else
combineB (mid + 1, r);
}
void solve ()
{
vector <int> ids;
for (int v = 1; v <= n; ++v)
{
C[i].clear();
mrk[v] = false;
}
int id = 0;
for (int v = 1; v <= n; ++v)
if (!mrk[v])
{
++id;
DFS (v, id);
ids.push_back (id);
}
int mid = (id - 1) / 2;
random_shuffle (ids.begin(), ids.end());
for (int v = 1; v <= n; ++v)
mrk[v] = false;
pA = 0;
for (int i = 0; i <= mid; ++i)
for (auto u: C[i])
A[pA++] = u;
pB = 0;
for (int i = mid + 1; i < id; ++i)
for (auto u: C[i])
B[pB++] = u;
combineA (0, pB - 1);
combineB (0, pA - 1);
setRoad (A[I], B[J]);
adj[A[I]].push_back (B[J]);
adj[B[J]].push_back (A[I]);
}
void run (int N)
{
n = N;
for (int i = 1; i <= n - 1; ++i)
{
if (N <= 15) acha ();
else if (N <= 50) aresta ();
else if (N <= 100) solve ();
}
}