| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 606282 |
2022-07-26T05:58:57 Z |
drdilyor |
ICC (CEOI16_icc) |
C++17 |
|
132 ms |
632 KB |
#include <bits/stdc++.h>
#ifdef ONPC
#include "t_debug.cpp"
#else
#define debug(...) 42
#include "icc.h"
#endif
#define sz(a) ((int)(a).size())
using namespace std;
using ll = long long;
const int INF = 1e9;
const ll INFL = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(123);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
const int N = 100, LOGN = 17, MOD = 1e9+7;
int nextPower2(int n) {
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return 1+n;
}
struct DSU {
int n;
vector<int> parent;
vector<int> size;
vector<vector<int>> full;
DSU(int n) : n(n), parent(n), size(n, 1), full(n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
full[i] = {i};
}
}
int get(int i) {
return parent[i] == i ? i : parent[i] = get(parent[i]);
}
void merge(int v, int u) {
v = get(v);
u = get(u);
if (u == v) return;
if (size[v] < size[u]) swap(v, u);
parent[u] = v;
size[v] += size[u];
for (int j : full[u]) {
full[v].push_back(j);
}
}
inline vector<int> elems(int i) {
return full[get(i)];
}
};
#ifdef ONPC
void setRoad(int u, int v);
#endif
void confirm(int u, int v);
int query(vector<int>&, vector<int>&);
int query(vector<int>&&, vector<int>&&);
int myrand(int i) {
return rng() % i;
}
void run(int n) {
DSU cc(n);
for (int e = 0; e < n-1; e++) {
vector<vector<int>> comps;
vector<int> visited(n);
for (int i = 0; i < n; i++) {
if (visited[cc.get(i)]) continue;
comps.push_back(cc.full[cc.get(i)]);
visited[cc.get(i)] = true;
}
sort(comps.begin(), comps.end(), [&](const vector<int>& a, const vector<int>& b) {
return a.size() < b.size();});
debug(cc.parent, cc.full);
debug(comps);
vector<int> a, b;
bool found = false;
vector<int> offs;
for (int off =nextPower2(sz(comps)) >> 1; off; off >>= 1) {
offs.push_back(off);
}
random_shuffle(offs.begin(), offs.end(), myrand);
function<tuple<vector<int>,vector<int>>(int)> partition = [&](int off) {
vector<int> a, b;
for (int i = 0; i < sz(comps); i++) {
if (i / off % 2 == 0) {
for (int j : comps[i]) a.push_back(j);
} else {
for (int j : comps[i]) b.push_back(j);
}
}
return tuple<vector<int>,vector<int>>{a, b};
};
for (int i = 0; i < sz(offs)-1; i++) {
tie(a, b) = partition(offs[i]);
if (query(a, b)) {found = true;break;}
}
if (!found) {
tie(a, b) = partition(offs.back());
}
while (sz(a) > 1) {
vector<int> a2;
for (int i = 0; i < sz(a) / 2; i++) {
a2.push_back(a[i]);
}
debug(a, a2);
if (!query(a2, b)) {
a2.clear();
for (int i = sz(a) / 2; i < sz(a); i++) {
a2.push_back(a[i]);
}
}
a = a2;
}
while (sz(b) > 1) {
vector<int> b2;
for (int i = 0; i < sz(b) / 2; i++) {
b2.push_back(b[i]);
}
if (!query(b2, a)) {
b2.clear();
for (int i = sz(b) / 2; i < sz(b); i++) {
b2.push_back(b[i]);
}
}
b = b2;
}
cc.merge(a.front(), b.front());
confirm(a.front(), b.front());
}
}
#ifdef ONPC
int n, m;
bool adj[N][N];
vector<pair<int,int>> edges;
int cur = 0;
int query_count = 0;
int query(vector<int>& a, vector<int>& b) {
++query_count;
bool res = false;
for (int i : a) {
for (int j : b) {
assert(i != j);
if (adj[i][j])res = true;
}
}
return res;
}
void advance() {
if (cur < sz(edges)) {
auto [u,v] = edges[cur];
adj[u][v] = adj[v][u] = true;
cur++;
}
}
void setRoad(int u, int v) {
if (u > v) swap(u, v);
if (edges[cur-1].first != u || edges[cur-1].second != v) {
debug("wrong guess", cur, edges[cur-1], u, v);
}
advance();
}
int solve() {
cin >> n >> m;
if (!cin) return 1;
memset(adj, 0, sizeof(adj));
edges.clear();
for (int i = 0; i < n-1; i++) {
int u, v; cin >> u >> v;
if (u > v) swap(u, v);
edges.emplace_back(u, v);
}
debug(edges);
advance();
run(n);
assert(cur == n-1);
debug(query_count);
return 0;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
#ifdef ONPC
t = 10000;
#endif
while (t-- && cin) {
if (solve()) break;
#ifdef ONPC
cout << "____________________" << endl;
#endif
}
return 0;
}
#else
int query(vector<int>& a, vector<int>& b) {
vector<int> a2 = a, b2 = b;
for (auto& i : a2) i++;
for (auto& i : b2) i++;
return query(a.size(), b.size(), a2.data(), b2.data());
}
#endif
void confirm(int u, int v){
#ifndef ONPC
u++; v++;
#endif
setRoad(u, v);
}
int query(vector<int>&& a, vector<int>&& b) {
return query(a, b);
}
/*
█████ █████ ███ ████
▒▒███ ▒▒███ ▒▒▒ ▒▒███
███████ ████████ ███████ ████ ▒███ █████ ████ ██████ ████████
███▒▒███ ▒▒███▒▒███ ███▒▒███ ▒▒███ ▒███ ▒▒███ ▒███ ███▒▒███▒▒███▒▒███
▒███ ▒███ ▒███ ▒▒▒ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒▒
▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███
▒▒████████ █████ ▒▒████████ █████ █████ ▒▒███████ ▒▒██████ █████
▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒███ ▒▒▒▒▒▒ ▒▒▒▒▒
███ ▒███
▒▒██████
▒▒▒▒▒▒
*/
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:5:24: warning: statement has no effect [-Wunused-value]
5 | #define debug(...) 42
| ^~
icc.cpp:85:9: note: in expansion of macro 'debug'
85 | debug(cc.parent, cc.full);
| ^~~~~
icc.cpp:5:24: warning: statement has no effect [-Wunused-value]
5 | #define debug(...) 42
| ^~
icc.cpp:86:9: note: in expansion of macro 'debug'
86 | debug(comps);
| ^~~~~
icc.cpp:5:24: warning: statement has no effect [-Wunused-value]
5 | #define debug(...) 42
| ^~
icc.cpp:122:13: note: in expansion of macro 'debug'
122 | debug(a, a2);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Ok! 98 queries used. |
| 2 |
Correct |
5 ms |
468 KB |
Ok! 96 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
484 KB |
Ok! 543 queries used. |
| 2 |
Correct |
32 ms |
468 KB |
Ok! 635 queries used. |
| 3 |
Correct |
32 ms |
468 KB |
Ok! 642 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
500 KB |
Ok! 1454 queries used. |
| 2 |
Correct |
105 ms |
500 KB |
Ok! 1585 queries used. |
| 3 |
Correct |
104 ms |
504 KB |
Ok! 1561 queries used. |
| 4 |
Correct |
127 ms |
520 KB |
Ok! 1549 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
516 KB |
Ok! 1552 queries used. |
| 2 |
Correct |
129 ms |
468 KB |
Ok! 1557 queries used. |
| 3 |
Correct |
99 ms |
516 KB |
Ok! 1572 queries used. |
| 4 |
Correct |
99 ms |
512 KB |
Ok! 1493 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
508 KB |
Ok! 1574 queries used. |
| 2 |
Correct |
107 ms |
468 KB |
Ok! 1584 queries used. |
| 3 |
Correct |
102 ms |
516 KB |
Ok! 1583 queries used. |
| 4 |
Correct |
104 ms |
500 KB |
Ok! 1577 queries used. |
| 5 |
Correct |
106 ms |
504 KB |
Ok! 1509 queries used. |
| 6 |
Correct |
109 ms |
504 KB |
Ok! 1571 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
632 KB |
Ok! 1590 queries used. |
| 2 |
Correct |
104 ms |
496 KB |
Ok! 1584 queries used. |
