| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521203 |
2022-02-01T08:09:49 Z |
79brue |
Park (JOI17_park) |
C++14 |
|
599 ms |
1920 KB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int query_arr[2002];
bool visited[2002];
int par[2002];
int depth[2002];
bool inRecursion[2002];
void query_select(vector<int>& v){
for(int i=0; i<n; i++) query_arr[i] = 0;
for(auto x: v) query_arr[x] = 1;
}
void solve(int x){
inRecursion[x] = 1;
/// 현재 방문한 곳만으로 접근 가능한지 판별
for(int i=0; i<n; i++){
query_arr[i] = visited[i];
}
query_arr[x] = 1;
if(Ask(0, x, query_arr)){ /// 접근 가능
vector<int> vec;
for(int i=0; i<n; i++) if(visited[i]) vec.push_back(i);
sort(vec.begin(), vec.end(), [&](int a, int b){
return depth[a] < depth[b];
});
int l = 0, r = (int)vec.size()-1;
while(l<r){
int m = (l+r)>>1;
memset(query_arr, 0, sizeof(query_arr));
vector<int> checklist;
for(int i=l; i<=m; i++){
checklist.push_back(vec[i]);
query_arr[vec[i]] = 1;
}
for(int i=0; i<(int)checklist.size(); i++){
if(checklist[i] && !query_arr[par[checklist[i]]]){
checklist.push_back(par[checklist[i]]);
query_arr[par[checklist[i]]] = 1;
}
}
query_arr[x] = 1;
bool ret = Ask(0, x, query_arr);
for(auto v: checklist) query_arr[v] = 0;
if(ret) r = m;
else l = m+1;
}
par[x] = vec[l];
Answer(min(par[x], x), max(par[x], x));
visited[x] = 1;
depth[x] = depth[par[x]] + 1;
}
else{
vector<int> vec;
for(int i=0; i<n; i++) if(!inRecursion[i] && x!=i) vec.push_back(i);
int l = 0, r = (int)vec.size()-1, qa = (int)vec.size() - 1;
while(l<=r){
int m = (l+r)>>1;
for(int i=0; i<=m; i++){
query_arr[vec[i]] = 1;
}
bool ret = Ask(0, x, query_arr);
for(int i=0; i<=m; i++){
query_arr[vec[i]] = 0;
}
if(ret){ /// 접근 가능 -> 줄여야 함
qa = m;
r = m-1;
}
else{
l = m+1;
}
}
solve(vec[qa]);
solve(x);
}
}
int deg[2002];
vector<int> link[2002];
bool chk[2002][2002];
void dfs_insert(int x, int p, vector<int>& v){
if(deg[x] < 7000) v.push_back(x);
for(auto y: link[x]){
if(p==y) continue;
dfs_insert(y, x, v);
}
}
void reorder(int x, int p = -1){
par[x] = p;
for(auto y: link[x]){
if(p==y) continue;
depth[y] = depth[x] + 1;
reorder(y, x);
}
}
void solve_cross(int o, int x, int p){ /// o - ... - p - x
if(deg[x] == 7) return;
vector<int> vec;
dfs_insert(x, p, vec);
int basel, l, r, qa;
retry:
if(vec.empty()) return;
query_select(vec), query_arr[o] = query_arr[x] = 1;
if(!Ask(min(o, x), max(o, x), query_arr)) return;
l = 0, r = (int)vec.size()-1, qa = (int)vec.size() - 1;
while(l<=r){
int m = (l+r)>>1;
memset(query_arr, 0, sizeof(query_arr));
query_arr[x] = query_arr[o] = 1;
vector<int> checklist;
for(int i=l; i<=m; i++){
checklist.push_back(vec[i]);
query_arr[vec[i]] = 1;
}
for(int i=0; i<(int)checklist.size(); i++){
if(par[checklist[i]] != p && !query_arr[par[checklist[i]]]){
query_arr[par[checklist[i]]] = 1;
checklist.push_back(par[checklist[i]]);
}
}
if(Ask(min(o, x), max(o, x), query_arr)){
qa = m;
r = m-1;
}
else l = m+1;
}
if(!chk[min(o, vec[qa])][max(o, vec[qa])]){
deg[o]++, deg[vec[qa]]++;
chk[min(o, vec[qa])][max(o, vec[qa])] = 1;
Answer(min(o, vec[qa]), max(o, vec[qa]));
}
for(auto nxt: link[vec[qa]]){
if(nxt == par[vec[qa]]) continue;
solve_cross(o, nxt, vec[qa]);
}
basel = qa+1;
while(basel < (int)vec.size() && depth[vec[basel]] > depth[vec[qa]]) basel++;
if(basel == (int)vec.size()) return;
vec.erase(vec.begin(), vec.begin() + basel);
goto retry;
}
void Detect(int t, int N){
n = N;
visited[0] = 1;
for(int i=1; i<n; i++){
if(visited[i]) continue;
solve(i);
}
for(int i=1; i<n; i++){
deg[i]++, deg[par[i]]++;
link[par[i]].push_back(i), link[i].push_back(par[i]);
}
for(int i=0; i<n; i++){
depth[i] = 0;
reorder(i);
for(auto j: link[i]){
for(auto k: link[j]){
if(k==i) continue;
solve_cross(i, k, j);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
468 KB |
Wrong Answer[6] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
599 ms |
744 KB |
Output is correct |
| 2 |
Correct |
198 ms |
524 KB |
Output is correct |
| 3 |
Correct |
274 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
557 ms |
668 KB |
Output is correct |
| 5 |
Correct |
556 ms |
700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
248 ms |
504 KB |
Output is correct |
| 2 |
Correct |
250 ms |
508 KB |
Output is correct |
| 3 |
Correct |
254 ms |
460 KB |
Output is correct |
| 4 |
Correct |
220 ms |
512 KB |
Output is correct |
| 5 |
Correct |
270 ms |
508 KB |
Output is correct |
| 6 |
Correct |
296 ms |
460 KB |
Output is correct |
| 7 |
Correct |
248 ms |
508 KB |
Output is correct |
| 8 |
Correct |
249 ms |
496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
460 KB |
Output is correct |
| 2 |
Correct |
309 ms |
556 KB |
Output is correct |
| 3 |
Correct |
317 ms |
544 KB |
Output is correct |
| 4 |
Correct |
386 ms |
564 KB |
Output is correct |
| 5 |
Correct |
347 ms |
708 KB |
Output is correct |
| 6 |
Correct |
413 ms |
640 KB |
Output is correct |
| 7 |
Correct |
424 ms |
716 KB |
Output is correct |
| 8 |
Correct |
305 ms |
564 KB |
Output is correct |
| 9 |
Correct |
355 ms |
564 KB |
Output is correct |
| 10 |
Correct |
405 ms |
624 KB |
Output is correct |
| 11 |
Correct |
392 ms |
684 KB |
Output is correct |
| 12 |
Correct |
295 ms |
600 KB |
Output is correct |
| 13 |
Correct |
430 ms |
596 KB |
Output is correct |
| 14 |
Correct |
384 ms |
616 KB |
Output is correct |
| 15 |
Correct |
407 ms |
600 KB |
Output is correct |
| 16 |
Correct |
254 ms |
460 KB |
Output is correct |
| 17 |
Correct |
551 ms |
668 KB |
Output is correct |
| 18 |
Correct |
375 ms |
620 KB |
Output is correct |
| 19 |
Correct |
437 ms |
632 KB |
Output is correct |
| 20 |
Correct |
358 ms |
564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
341 ms |
1072 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
