| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 821598 |
2023-08-11T11:58:55 Z |
AdamGS |
Park (JOI17_park) |
C++17 |
|
121 ms |
1924 KB |
#include "park.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1407;
static int Place[1400];
vector<int>V[LIM], pos;
int odw[LIM], n, ile;
void DFS(int x, int o) {
for(auto i : V[x]) if(i!=o) DFS(i, x);
pos.pb(x);
}
int znajdz_ojca(int x) {
pos.clear();
DFS(0, 0);
reverse(all(pos));
int po=0, ko=(int)pos.size()-1;
while(po<ko) {
int sr=(po+ko)/2;
rep(i, n) Place[i]=0;
rep(i, sr+1) Place[pos[i]]=1;
rep(i, n) if(!odw[i]) Place[i]=1;
if(Ask(0, x, Place)) ko=sr; else po=sr+1;
}
return pos[po];
}
void sciezka(int a, int b) {
rep(i, n) Place[i]=0;
Place[a]=Place[b]=1;
if(Ask(min(a, b), max(a, b), Place)) {
odw[b]=1; ++ile;
V[a].pb(b);
V[b].pb(a);
Answer(min(a, b), max(a, b));
return;
}
vector<int>T;
rep(i, n) if(!odw[i] && i!=b) T.pb(i);
int po=0, ko=(int)T.size()-1;
while(po<ko) {
int sr=(po+ko)/2;
rep(i, n) Place[i]=0;
rep(i, sr+1) Place[T[i]]=1;
Place[a]=Place[b]=1;
if(Ask(min(a, b), max(a, b), Place)) ko=sr; else po=sr+1;
}
sciezka(a, T[po]);
sciezka(T[po], b);
}
void Detect(int T, int N) {
n=N;
odw[0]=ile=1;
while(ile<n) {
int x=-1;
rep(i, n) if(!odw[i]) {
x=i;
break;
}
int p=znajdz_ojca(x);
sciezka(p, x);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
596 KB |
Output is correct |
| 2 |
Correct |
76 ms |
540 KB |
Output is correct |
| 3 |
Correct |
64 ms |
1924 KB |
Output is correct |
| 4 |
Correct |
26 ms |
576 KB |
Output is correct |
| 5 |
Correct |
26 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
480 KB |
Output is correct |
| 2 |
Correct |
121 ms |
468 KB |
Output is correct |
| 3 |
Correct |
71 ms |
488 KB |
Output is correct |
| 4 |
Correct |
71 ms |
468 KB |
Output is correct |
| 5 |
Correct |
69 ms |
500 KB |
Output is correct |
| 6 |
Correct |
71 ms |
492 KB |
Output is correct |
| 7 |
Correct |
78 ms |
468 KB |
Output is correct |
| 8 |
Correct |
71 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
340 KB |
Output is correct |
| 2 |
Correct |
110 ms |
536 KB |
Output is correct |
| 3 |
Correct |
67 ms |
468 KB |
Output is correct |
| 4 |
Correct |
57 ms |
556 KB |
Output is correct |
| 5 |
Correct |
54 ms |
616 KB |
Output is correct |
| 6 |
Correct |
56 ms |
636 KB |
Output is correct |
| 7 |
Correct |
81 ms |
608 KB |
Output is correct |
| 8 |
Correct |
64 ms |
556 KB |
Output is correct |
| 9 |
Correct |
65 ms |
536 KB |
Output is correct |
| 10 |
Correct |
95 ms |
572 KB |
Output is correct |
| 11 |
Correct |
96 ms |
632 KB |
Output is correct |
| 12 |
Correct |
74 ms |
600 KB |
Output is correct |
| 13 |
Correct |
45 ms |
596 KB |
Output is correct |
| 14 |
Correct |
74 ms |
632 KB |
Output is correct |
| 15 |
Correct |
40 ms |
596 KB |
Output is correct |
| 16 |
Correct |
74 ms |
480 KB |
Output is correct |
| 17 |
Correct |
26 ms |
612 KB |
Output is correct |
| 18 |
Correct |
69 ms |
728 KB |
Output is correct |
| 19 |
Correct |
39 ms |
596 KB |
Output is correct |
| 20 |
Correct |
60 ms |
548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
556 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
