#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 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;
}
}
}
int pA, A[maxn];
int pB, B[maxn];
int pC, C[maxn];
int nodes[2];
void combine (int id, int l, int r)
{
if (l == r)
{
nodes[id] = B[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))
combine (id, l, mid);
else
combine (id, mid + 1, r);
}
void solve ()
{
for (int v = 1; v <= n; ++v)
{
c[0] = v;
for (int u = 1; u <= n; ++u)
mrk[u] = false;
dfs (v);
pA = 0;
for (int u = 1; u <= n; ++u)
if (mrk[u])
A[++pA] = u;
pB = 0;
for (int u = 1; u <= n; ++u)
if (!mrk[u])
B[pB++] = u;
if (query (pA, pB, A, B))
{
combine (0, 0, pB - 1);
for (int u = 1; u <= n; ++u)
mrk[u] = false;
dfs (nodes[0]);
for (int i = 1; i <= n; ++i)
if (!mrk[i])
{
c[0] = i;
d[0] = nodes[0];
if (query (1, 1, c, d))
{
nodes[1] = i;
break;
}
}
adj[nodes[0]].push_back (nodes[1]);
adj[nodes[1]].push_back (nodes[0]);
setRoad (nodes[0], nodes[1]);
return;
}
}
}
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 ();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
2092 KB |
Ok! 1015 queries used. |
2 |
Correct |
59 ms |
2092 KB |
Ok! 1010 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
103 ms |
2092 KB |
Ok! 1508 queries used. |
2 |
Correct |
106 ms |
2092 KB |
Ok! 1483 queries used. |
3 |
Correct |
116 ms |
2088 KB |
Ok! 1517 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2056 KB |
Query cities not in range [1, n] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2056 KB |
Query cities not in range [1, n] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2056 KB |
Query cities not in range [1, n] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2056 KB |
Query cities not in range [1, n] |
2 |
Halted |
0 ms |
0 KB |
- |