oj.uz

Submission #1026309

# Submission time Handle Problem Language Result Execution time Memory
1026309 2024-07-17T20:04:21 Z Antekb Park (JOI17_park) C++17
100 / 100
 213 ms 4688 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};
	rest.resize(n-1);
	iota(all(rest), 1);
	while(rest.size()){
		int t=rest.back();
		rest.pop_back();
		vi V=bfs(0);
		for(int i:V){
			dist[i]=0;
			Place[i]=1;
		}
		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);
	}
	for(int i=0; i<n; i++){
		Place[i]=0;
		dist[i]=0;
		blocked[i]=0;
		E[i].clear();
	}
}

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++){
      |               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 25 ms 576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 756 KB Output is correct
2 Correct 152 ms 4688 KB Output is correct
3 Correct 130 ms 3412 KB Output is correct
4 Correct 124 ms 604 KB Output is correct
5 Correct 115 ms 604 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 604 KB Output is correct
2 Correct 140 ms 604 KB Output is correct
3 Correct 150 ms 904 KB Output is correct
4 Correct 136 ms 604 KB Output is correct
5 Correct 134 ms 636 KB Output is correct
6 Correct 128 ms 616 KB Output is correct
7 Correct 130 ms 604 KB Output is correct
8 Correct 143 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 624 KB Output is correct
2 Correct 146 ms 604 KB Output is correct
3 Correct 149 ms 660 KB Output is correct
4 Correct 158 ms 604 KB Output is correct
5 Correct 148 ms 604 KB Output is correct
6 Correct 126 ms 652 KB Output is correct
7 Correct 130 ms 604 KB Output is correct
8 Correct 146 ms 604 KB Output is correct
9 Correct 162 ms 604 KB Output is correct
10 Correct 159 ms 856 KB Output is correct
11 Correct 162 ms 604 KB Output is correct
12 Correct 168 ms 604 KB Output is correct
13 Correct 136 ms 684 KB Output is correct
14 Correct 148 ms 676 KB Output is correct
15 Correct 138 ms 688 KB Output is correct
16 Correct 128 ms 604 KB Output is correct
17 Correct 129 ms 604 KB Output is correct
18 Correct 150 ms 604 KB Output is correct
19 Correct 135 ms 704 KB Output is correct
20 Correct 145 ms 696 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 636 KB Output is correct
2 Correct 181 ms 600 KB Output is correct
3 Correct 142 ms 616 KB Output is correct
4 Correct 150 ms 692 KB Output is correct
5 Correct 179 ms 604 KB Output is correct
6 Correct 121 ms 604 KB Output is correct
7 Correct 213 ms 952 KB Output is correct
8 Correct 136 ms 604 KB Output is correct
9 Correct 139 ms 728 KB Output is correct
10 Correct 147 ms 680 KB Output is correct
11 Correct 143 ms 604 KB Output is correct
12 Correct 166 ms 604 KB Output is correct
13 Correct 138 ms 648 KB Output is correct
14 Correct 183 ms 604 KB Output is correct
15 Correct 138 ms 604 KB Output is correct
16 Correct 124 ms 604 KB Output is correct
17 Correct 112 ms 604 KB Output is correct
18 Correct 135 ms 604 KB Output is correct