| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026305 |
2024-07-17T19:50:25 Z |
Antekb |
Park (JOI17_park) |
C++17 |
|
200 ms |
4692 KB |
#include "park.h"
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
const int N=1400;
static int Place[N];
int dist[N], blocked[N];
vi E[N];
bool ask(int a, int b){
assert(a!=b);
assert(Place[a]);
assert(Place[b]);
return Ask(min(a, b), max(a, b), Place);
}
vector<int> bfs(int root){
vector<int> V;
V.push_back(root);
dist[root]=1;
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int u:E[v]){
if(!dist[u] && !blocked[u]){
dist[u]=dist[v]+1;
V.pb(u);
}
}
}
return V;
}
void find_edges(int root, int v, bool is_root=0){
vi V=bfs(root);
deb(root, v, V);
for(int i:V)dist[i]=0;
for(int i:V)Place[i]=1;
Place[v]=1;
if(!ask(root, v)){
assert(!is_root);
return;
}
int l=1, r=SZ(V);
while(l<r){
int m=(l+r)/2;
for(int i=0; i<m; i++){
Place[V[i]]=1;
}
for(int i=m; i<SZ(V); i++){
Place[V[i]]=0;
}
if(ask(root, v))r=m;
else l=m+1;
}
int u=V[l-1];
E[v].pb(u);
E[u].pb(v);
Answer(min(v, u), max(u, v));
vi rec;
blocked[u]=1;
for(int w:E[u]){
if(!dist[w] && !blocked[w]){
rec.pb(w);
bfs(w);
}
}
for(int i:V)dist[i]=0;
for(int i:V)Place[i]=0;
Place[v]=0;
for(int i:rec){
find_edges(i, v);
}
blocked[u]=0;
}
vi gen_chain(int s, int t, vector<int> V){
deb(s, t, V);
int l=0, r=V.size();
while(l<r){
int m=(l+r)/2;
for(int i=0; i<m; i++){
Place[V[i]]=1;
}
for(int i=m; i<SZ(V); i++){
Place[V[i]]=0;
}
deb(s, t, Place[s], Place[t]);
if(ask(s, t))r=m;
else l=m+1;
}
for(int i:V)Place[i]=0;
if(l==0){
deb(t);
return {t};
}
else{
int mid=V[l-1];
V.resize(l-1);
Place[mid]=1;
vi A=gen_chain(s, mid, V);
vi B=gen_chain(mid, t, V);
for(int i:B)A.pb(i);
deb(A);
return A;
}
}
void Detect(int T, int n) {
vector<int> comp, rest;
comp={0};
Place[0]=1;
rest.resize(n-1);
iota(all(rest), 1);
while(rest.size()){
int t=rest.back();
rest.pop_back();
Place[t]=1;
vector<int> todo=gen_chain(0, t, rest);
deb(todo);
for(int i:todo){
if(i!=t)rest.erase(find(all(rest), i));
fill(Place, Place+n, 0);
blocked[i]=1;
find_edges(0, i, 1);
blocked[i]=0;
comp.push_back(i);
}
deb(todo);
}
}
Compilation message
park.cpp:19:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
park.cpp:19:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
park.cpp:19:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
park.cpp:21:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
21 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
park.cpp:21:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
21 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
park.cpp: In function 'std::vector<int> bfs(int)':
park.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
728 KB |
Output is correct |
| 2 |
Correct |
200 ms |
4692 KB |
Output is correct |
| 3 |
Correct |
143 ms |
3292 KB |
Output is correct |
| 4 |
Correct |
126 ms |
604 KB |
Output is correct |
| 5 |
Correct |
128 ms |
744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
2520 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
2132 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
130 ms |
1108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
