| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 604437 |
2022-07-25T06:28:24 Z |
SeDunion |
ICC (CEOI16_icc) |
C++17 |
|
1 ms |
468 KB |
#include<icc.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int N = 103;
int p[N];
int get(int x) {
if (x == p[x]) return x;
return p[x] = get(p[x]);
}
int A[N], B[N];
int query(vector<int>&X, vector<int>&Y) {
for (int i = 0 ; i < (int)X.size() ; ++ i) A[i] = X[i];
for (int i = 0 ; i < (int)Y.size() ; ++ i) B[i] = Y[i];
return query(X.size(), Y.size(), A, B);
}
void run(int N) {
for (int i = 1 ; i <= N ; ++ i) p[i] = i;
for (int rep = 0 ; rep < N - 1 ; ++ rep) {
vector<int>cur;
for (int i = 1 ; i <= N ; ++ i) cur.emplace_back(get(i));
sort(cur.begin(), cur.end()); cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
int m = cur.size();
int diff = 0;
for (int b = 1 ; b <= m ; b <<= 1) {
vector<int>A, B;
for (int i = 0 ; i < m ; ++ i) {
if (i >> b & 1) A.emplace_back(cur[i]);
else B.emplace_back(cur[i]);
}
if (A.empty() || B.empty()) continue;
int x = query(A, B);
if (x) diff |= b;
}
vector<pair<int,int>>can;
for (int i = 0 ; i < m ; ++ i) {
int x = cur[i];
int y = (cur[i] ^ diff);
if (1 <= y && y <= N) {
can.emplace_back(x, y);
}
}
int l = 0, r = (int)can.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
vector<int>A, B;
for (int i = 0 ; i <= mid ; ++ i) {
A.emplace_back(can[i].first);
B.emplace_back(can[i].second);
}
int x = query(A, B);
if (x) r = mid;
else l = mid + 1;
}
int x = can[r].first;
int y = can[r].second;
vector<int>X, Y;
for (int i = 1 ; i <= N ; ++ i) {
if (get(i) == x) X.emplace_back(i);
if (get(i) == y) Y.emplace_back(i);
}
int lx = 0, rx = (int)X.size() - 1;
while (lx < rx) {
int mid = (lx + rx) >> 1;
vector<int>A, B = Y;
for (int i = 0 ; i <= mid ; ++ i) {
A.emplace_back(X[i]);
}
int x = query(A, B);
if (x) rx = mid;
else lx = mid + 1;
}
int ly = 0, ry = (int)Y.size() - 1;
while (ly < ry) {
int mid = (ly + ry) >> 1;
vector<int>A = X, B;
for (int i = 0 ; i <= mid ; ++ i) {
B.emplace_back(Y[i]);
}
int x = query(A, B);
if (x) ry = mid;
else ly = mid + 1;
}
int a = X[rx];
int b = Y[ry];
cout << "edge " << a << " " << b << endl;
p[a] = b;
setRoad(a, b);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
