| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 604484 | SeDunion | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<algorithm>
#include<iostream>
#include<vector>
#ifndef LOCAL
#include<icc.h>
#endif
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 rx[N], ry[N], rr;
int road[N][N];
#ifndef LOCAL
void setRoad(int a, int b) {
++rr;
cout << "New road " << rx[rr] << " " << ry[rr] << endl;
road[rx[rr]][ry[rr]] = road[ry[rr]][rx[rr]] = 1;
}
#endif
int query(vector<int>&X, vector<int>&Y) {
#ifndef LOCAL
cout << "Q: ";
for (int i : X) cout << i << " ";
cout << "\n ";
for (int i : Y) cout << i << " ";
cout << endl;
for (int i : X) for (int j : Y) {
if (road[i][j]) {
cout << "TRUE\n";
return 1;
}
}
cout << "FALSE\n";
return 0;
#else
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);
#endif
}
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;
#ifndef LOCAL
cout << "cur ";
for (int i : cur) cout << i << " ";
cout << endl;
#endif
for (int b = 0 ; b < 10 ; ++ b) {
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;
for (int i = 1 ; i <= N ; ++ i) {
if (count(A.begin(), A.end(), i) == 0 && count(A.begin(), A.end(), get(i)) == 1) {
A.emplace_back(i);
}
if (count(B.begin(), B.end(), i) == 0 && count(B.begin(), B.end(), get(i)) == 1) {
B.emplace_back(i);
}
}
int x = query(A, B);
if (x) diff |= 1 << b;
}
#ifndef LOCAL
cout << "diff " << diff << endl;
#endif
vector<pair<int,int>>can;
for (int i = 0 ; i < m ; ++ i) {
int x = cur[i];
int j = (i ^ diff);
if (0 <= j && j < m); else continue;
int y = cur[j];
if (1 <= y && y <= N) {
bool has = false;
for (auto [a, b] : can) {
if (a == x && b == y) has = true;
if (a == y && b == x) has = true;
}
if (has) continue;
for (int i = 1 ; i <= N ; ++ i) {
for (int j = 1 ; j <= N ; ++ j) {
if (get(i) == x && get(j) == y) {
can.emplace_back(i, j);
}
}
}
}
}
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;
#ifndef LOCAL
cout << "GUESS ROAD " << x << " " << y << endl;
#endif
p[get(x)] = get(y);
setRoad(x, y);
/*
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 << "GUESS ROAD " << a << " " << b << endl;
p[get(a)] = get(b);
setRoad(a, b);
*/
}
}
#ifndef LOCAL
int main() {
int n;
cin >> n;
for (int rep = 0 ; rep < n - 1 ; ++ rep) {
cin >> rx[rep] >> ry[rep];
}
road[rx[0]][ry[0]] = road[ry[0]][rx[0]] = 1;
run(n);
}
#endif