| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 566119 |
2022-05-21T20:20:05 Z |
piOOE |
ICC (CEOI16_icc) |
C++17 |
|
108 ms |
652 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
int ask(vector<int> a, vector<int> b) {
for (int &x: a) ++x;
for (int &y: b) ++y;
return query(sz(a), sz(b), a.data(), b.data());
}
vector<int> p;
int get(int a) {
return a == p[a] ? a : p[a] = get(p[a]);
}
bool mrg(int a, int b) {
a = get(a), b = get(b);
if (a == b) {
return false;
}
p[b] = a;
return true;
}
void run(int n) {
p.resize(n);
iota(all(p), 0);
for (int cnt = 1; cnt < n; ++cnt) {
vector<int> v;
for (int i = 0; i < n; ++i) {
if (p[i] == i) v.push_back(i);
}
assert(sz(p) > 1);
vector<vector<int>> f, s;
f.emplace_back(), s.emplace_back();
for (int i = 0; i < sz(v); ++i) {
if (i & 1) s.back().push_back(v[i]);
else f.back().push_back(v[i]);
}
map<int, vector<int>> lst;
for (auto a: f.back())
lst[a] = s.back();
for (auto a: s.back())
lst[a] = f.back();
while (true) {
vector<int> a, b;
for (auto &x: f) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) a.push_back(i);
}
}
}
for (auto &x: s) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) b.push_back(i);
}
}
}
if (ask(a, b)) break;
lst.clear();
vector<vector<int>> ff, ss;
for (auto &x: f) {
ff.emplace_back();
ss.emplace_back();
for (int i = 0; i < sz(x); ++i) {
if (i & 1) ss.back().push_back(x[i]);
else ff.back().push_back(x[i]);
}
if (ss.back().empty()) {
ss.pop_back();
continue;
}
if (ff.back().empty()) {
ff.pop_back();
continue;
}
for (auto aa: ff.back())
lst[aa] = ss.back();
for (auto aa: ss.back())
lst[aa] = ff.back();
}
for (auto &x: s) {
ff.emplace_back();
ss.emplace_back();
for (int i = 0; i < sz(x); ++i) {
if (i & 1) ss.back().push_back(x[i]);
else ff.back().push_back(x[i]);
}
if (ss.back().empty()) {
ss.pop_back();
continue;
}
if (ff.back().empty()) {
ff.pop_back();
continue;
}
for (auto aa: ff.back())
lst[aa] = ss.back();
for (auto aa: ss.back())
lst[aa] = ff.back();
}
swap(f, ff);
swap(s, ss);
}
{
vector<int> a, b;
for (auto &x: f) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) a.push_back(i);
}
}
}
for (auto &x: s) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) b.push_back(i);
}
}
}
int l = 0, r = sz(b);
while (l + 1 < r) {
int m = (l + r) >> 1;
vector<int> c;
for (int i = l; i < m; ++i) {
c.push_back(b[i]);
}
if (ask(a, c)) r = m;
else l = m;
}
int v1 = b[l];
{
auto xx = lst[get(v1)];
a.clear();
for (int y: xx) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) a.push_back(i);
}
}
}
l = 0, r = sz(a);
while (l + 1 < r) {
int m = (l + r) >> 1;
vector<int> c;
for (int i = l; i < m; ++i) {
c.push_back(a[i]);
}
if (ask({v1}, c)) r = m;
else l = m;
}
int v2 = a[l];
setRoad(v1 + 1, v2 + 1);
mrg(v1, v2);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Ok! 94 queries used. |
| 2 |
Correct |
4 ms |
468 KB |
Ok! 96 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
504 KB |
Ok! 512 queries used. |
| 2 |
Correct |
30 ms |
520 KB |
Ok! 499 queries used. |
| 3 |
Correct |
28 ms |
520 KB |
Ok! 514 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
540 KB |
Ok! 1275 queries used. |
| 2 |
Correct |
105 ms |
524 KB |
Ok! 1230 queries used. |
| 3 |
Correct |
103 ms |
540 KB |
Ok! 1176 queries used. |
| 4 |
Correct |
103 ms |
560 KB |
Ok! 1264 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
588 KB |
Ok! 1232 queries used. |
| 2 |
Correct |
102 ms |
468 KB |
Ok! 1239 queries used. |
| 3 |
Correct |
106 ms |
648 KB |
Ok! 1230 queries used. |
| 4 |
Correct |
99 ms |
532 KB |
Ok! 1254 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
544 KB |
Ok! 1249 queries used. |
| 2 |
Correct |
103 ms |
652 KB |
Ok! 1227 queries used. |
| 3 |
Correct |
106 ms |
524 KB |
Ok! 1231 queries used. |
| 4 |
Correct |
106 ms |
532 KB |
Ok! 1243 queries used. |
| 5 |
Correct |
99 ms |
548 KB |
Ok! 1265 queries used. |
| 6 |
Correct |
106 ms |
536 KB |
Ok! 1241 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
540 KB |
Ok! 1227 queries used. |
| 2 |
Correct |
102 ms |
536 KB |
Ok! 1230 queries used. |
