| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521188 |
2022-02-01T07:50:08 Z |
79brue |
Park (JOI17_park) |
C++14 |
|
578 ms |
1980 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);
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;
int basel = 0, l, r, qa;
retry:
l = basel, 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;
goto retry;
}
void Detect(int t, int N){
n = N;
assert(n>10);
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 |
Incorrect |
1 ms |
332 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
550 ms |
632 KB |
Output is correct |
| 2 |
Correct |
195 ms |
492 KB |
Output is correct |
| 3 |
Correct |
278 ms |
1980 KB |
Output is correct |
| 4 |
Correct |
578 ms |
672 KB |
Output is correct |
| 5 |
Correct |
556 ms |
812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
460 KB |
Output is correct |
| 2 |
Correct |
246 ms |
504 KB |
Output is correct |
| 3 |
Correct |
303 ms |
508 KB |
Output is correct |
| 4 |
Correct |
232 ms |
496 KB |
Output is correct |
| 5 |
Correct |
270 ms |
504 KB |
Output is correct |
| 6 |
Correct |
258 ms |
504 KB |
Output is correct |
| 7 |
Correct |
265 ms |
516 KB |
Output is correct |
| 8 |
Correct |
250 ms |
580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
472 KB |
Output is correct |
| 2 |
Correct |
331 ms |
544 KB |
Output is correct |
| 3 |
Correct |
320 ms |
540 KB |
Output is correct |
| 4 |
Correct |
374 ms |
560 KB |
Output is correct |
| 5 |
Correct |
376 ms |
596 KB |
Output is correct |
| 6 |
Correct |
425 ms |
664 KB |
Output is correct |
| 7 |
Correct |
406 ms |
676 KB |
Output is correct |
| 8 |
Correct |
335 ms |
568 KB |
Output is correct |
| 9 |
Correct |
337 ms |
556 KB |
Output is correct |
| 10 |
Correct |
434 ms |
588 KB |
Output is correct |
| 11 |
Correct |
387 ms |
704 KB |
Output is correct |
| 12 |
Correct |
298 ms |
600 KB |
Output is correct |
| 13 |
Correct |
443 ms |
596 KB |
Output is correct |
| 14 |
Correct |
353 ms |
624 KB |
Output is correct |
| 15 |
Correct |
401 ms |
712 KB |
Output is correct |
| 16 |
Correct |
279 ms |
504 KB |
Output is correct |
| 17 |
Correct |
545 ms |
776 KB |
Output is correct |
| 18 |
Correct |
374 ms |
608 KB |
Output is correct |
| 19 |
Correct |
438 ms |
668 KB |
Output is correct |
| 20 |
Correct |
325 ms |
564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
552 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
