oj.uz

Submission #520996

# Submission time Handle Problem Language Result Execution time Memory
520996 2022-01-31T15:32:14 Z koioi.org-koosaga Park (JOI17_park) C++17
100 / 100
 362 ms 804 KB 
#include "park.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 1500;

static int Place[1400];

vector<int> gph[MAXN];
vector<int> ord;

int vis[MAXN], sz[MAXN];

void dfs(int x){
	vis[x] = 1;
	sz[x] = 1;
	ord.push_back(x);
	for(auto &y : gph[x]){
		if(!vis[y]){
			dfs(y);
			sz[x] += sz[y];
		}
	}
}

void go(int s, int e, int x, int n){
//	cout <<"go " <<  s << " " << e << " " << x << endl;

	set<int> banned;
	while(banned.count(s) == 0){
		// see if there exists edge in first place (called N+8M times)
		{
			for(int i = 0; i < n; i++) Place[i] = 0;
			for(int i = s; i <= e; i++){
				if(banned.count(i)) continue;
				Place[ord[i]] = 1;
			}
			Place[x] = 1;
			if(Ask(min(ord[s], x), max(ord[s], x), Place) == 0) return;
		}
		// find first position where you can have connection (called M times)
		int connPoint = -1;
		{
			int ns = s, ne = e;
			while(ns != ne){
				int m = (ns + ne) / 2;
				for(int i = 0; i < n; i++) Place[i] = 0;
				Place[ord[s]] = Place[x] = 1;
				for(int i = s; i <= m; i++){
					if(banned.count(i)) continue;
					Place[ord[i]] = 1;
				}
				if(Ask(min(ord[s], x), max(ord[s], x), Place) == 1) ne = m;
				else ns = m + 1;
			}
			connPoint = ns;
		}
		// add edge
		int y = ord[connPoint];
		gph[x].push_back(y);
//		cout << "found edge " << x << " " << y << endl;
		// ban 
		for(int i = connPoint; i <= connPoint + sz[y] - 1; i++){
			banned.insert(i);
		}
		int pos = connPoint + 1;
		while(pos <= connPoint + sz[y] - 1){
			go(pos, pos + sz[ord[pos]] - 1, x, n);
			pos += sz[ord[pos]];
		}
	}
}

void Detect(int T, int N) {
	vector<int> v = {};
	for(int i = 1; i < N; i++){
		auto init = [&](){
			memset(Place, 0, sizeof(Place));
			for(int i = 0; i < N; i++) Place[i] = 1;
		};
		int s = 0, e = sz(v);
		while(s != e){
			int m = (s + e) / 2;
			init();
			for(int i = m; i < sz(v); i++) Place[v[i]] = 0;
			if(Ask(0, i, Place) == 1) e = m;
			else s = m + 1;
		}
		v.insert(v.begin() + s, i);
	}
//	for(auto &i : v) cout << i << " ";
//	cout << "ok??" << endl;
	for(int i = 0; i < sz(v); i++){
		ord.clear();
		memset(sz, 0, sizeof(sz));
		memset(vis, 0, sizeof(vis));
		dfs(0);
		go(0, sz(ord) - 1, v[i], N);
		for(auto &j : gph[v[i]]) gph[j].push_back(v[i]);
	}
	for(int i = 0; i < N; i++){
		for(auto &j : gph[i]) if(i < j) Answer(i, j);
		gph[i].clear();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 9 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 26 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 672 KB Output is correct
2 Correct 190 ms 528 KB Output is correct
3 Correct 192 ms 464 KB Output is correct
4 Correct 356 ms 656 KB Output is correct
5 Correct 355 ms 568 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 548 KB Output is correct
2 Correct 253 ms 472 KB Output is correct
3 Correct 261 ms 604 KB Output is correct
4 Correct 273 ms 504 KB Output is correct
5 Correct 252 ms 436 KB Output is correct
6 Correct 249 ms 708 KB Output is correct
7 Correct 246 ms 436 KB Output is correct
8 Correct 242 ms 464 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 408 KB Output is correct
2 Correct 262 ms 460 KB Output is correct
3 Correct 278 ms 516 KB Output is correct
4 Correct 288 ms 512 KB Output is correct
5 Correct 244 ms 484 KB Output is correct
6 Correct 313 ms 600 KB Output is correct
7 Correct 291 ms 452 KB Output is correct
8 Correct 262 ms 436 KB Output is correct
9 Correct 265 ms 680 KB Output is correct
10 Correct 302 ms 452 KB Output is correct
11 Correct 285 ms 592 KB Output is correct
12 Correct 281 ms 452 KB Output is correct
13 Correct 274 ms 496 KB Output is correct
14 Correct 305 ms 700 KB Output is correct
15 Correct 254 ms 436 KB Output is correct
16 Correct 277 ms 420 KB Output is correct
17 Correct 361 ms 560 KB Output is correct
18 Correct 283 ms 508 KB Output is correct
19 Correct 311 ms 724 KB Output is correct
20 Correct 256 ms 452 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 704 KB Output is correct
2 Correct 340 ms 568 KB Output is correct
3 Correct 264 ms 444 KB Output is correct
4 Correct 289 ms 524 KB Output is correct
5 Correct 321 ms 576 KB Output is correct
6 Correct 348 ms 776 KB Output is correct
7 Correct 318 ms 516 KB Output is correct
8 Correct 362 ms 664 KB Output is correct
9 Correct 303 ms 532 KB Output is correct
10 Correct 306 ms 528 KB Output is correct
11 Correct 256 ms 520 KB Output is correct
12 Correct 333 ms 512 KB Output is correct
13 Correct 251 ms 804 KB Output is correct
14 Correct 358 ms 640 KB Output is correct
15 Correct 303 ms 588 KB Output is correct
16 Correct 260 ms 432 KB Output is correct
17 Correct 344 ms 464 KB Output is correct
18 Correct 284 ms 648 KB Output is correct