| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1282708 | nikaa123 | Park (JOI17_park) | C++20 | 0 ms | 0 KiB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
// #define int int
// int p[1405];
int f[1505];
int n;
static int p[1505];
vector <int> lst, nodes,vis(1505);
vector <vector<int>> v(1505);
void colect(int x) {
if (vis[x]) return;
nodes.push_back(x);
for (auto to:v[x]) {
if (f[i] && !vis[to]) colect(to);
}
}
void dfs(int x, int node) {
while (true) {
if (vis[x]) return;
nodes.clear();
colect(x);
for (int i = 0; i < n; i++) {
p[i] = 0;
}
for (auto to:nodes) {
p[to] = 1;
}
p[node] = p[x] = 1;
if (!Ask(min(node,x),max(node,x),p)) {
return;
}
int l = 0; int r =(int)(nodes.size())-1;
int res = -1;
while (l <= r) {
int mid = (l+r)/2;
for (int i = 0; i < n; i++) {
p[i] = 0;
}
for (int i = 0; i <= mid; i++) {
p[nodes[i]] = 1;
}
p[node] = p[x] = 1;
if (Ask(min(node,x),max(node,x),p)) {
res = nodes[mid];
r = mid - 1;
} else {
l = mid + 1;
}
}
vis[res] = 1;
lst.push_back(res);
for (auto to:v[res]) {
dfs(to,node);
}
}
}
void explore(int x) {
if (f[x]) {
return;
}
for (int i = 0; i < n; i++) {
p[i] = f[i];
}
p[x] = 1;
p[0] = 1;
while (!Ask(0,x,p)) {
int l = 0; int r = n-1;
int res = -1;
while (l <= r) {
int mid = (l+r)/2;
for (int i = 0; i < n; i++) {
if (f[i] || (i<= mid)) {
p[i] = 1;
} else {
p[i] = 0;
}
}
p[x] = 1;
p[0] = 1;
if (Ask(0,x,p)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
explore(res);
}
for (int i = 0; i < n; i++) {
vis[i] = 0;
}
lst.clear();
dfs(0,x);
for (auto u:lst) {
Answer(min(u,x),max(u,x));
}
if (!lst.empty()) v[lst[0]].push_back(x);
f[x] = 1;
}
void Detect(int T, int N) {
n = N;
for (int i = 0; i < n; i++) {
f[i] = 0;
p[i] = 0;
vis[i] = 0;
v[i].clear();
}
f[0] = 1;
for (int i = 0; i < n; i++) {
if (f[i]) continue;
explore(i);
}
}