# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24628 | 2017-06-10T18:58:02 Z | bill_kondo | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KB |
#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 v, int l, int r) { if (l == r) { node = 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 (v, l, mid); else combina (v, 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 (v, 0, pointer - 1); adj[v].push_back (node); adj[node].push_back (v); setRoad (v, node); return; } } } void run (int N) { n = N; for (int i = 1; i <= n - 1; ++i) { if (N <= 15) acha (); else if (N <= 50) aresta (); } }