oj.uz

Submission #430859

# Submission time Handle Problem Language Result Execution time Memory
430859 2021-06-17T07:11:38 Z 8e7 Park (JOI17_park) C++14
77 / 100
 302 ms 628 KB 
#include "park.h"
//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <random>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 1405
#define mod 1000000007
#define pii pair<long long, long long>
#define ff first
#define ss second

static int que[maxn];
vector<pii> ed;
vector<int> adj[maxn], vert;
int ord[maxn];
bool found[maxn];
int qcnt = 0;
int query(int a, int b) {
	if (a > b) swap(a, b);
	if (a == b || (que[a] == 0) || (que[b] == 0)) return 0;
	qcnt++;
	return Ask(a, b, que);
}
vector<int> chain(vector<int> v) {
	if (v.size() <= 3) return v;
	int piv = v[1 + rand() % (v.size() - 2)];
	vector<int> lef, rig;
	lef.push_back(v[0]), rig.push_back(piv);
	for (int i:v) que[i] = 1;
	que[piv] = 0;
	for (int i = 1;i < v.size() - 1;i++) {
		if (v[i] != piv && query(v[0], v[i])) lef.push_back(v[i]);
		else if (v[i] != piv) rig.push_back(v[i]);
	}
	lef.push_back(piv), rig.push_back(v.back());
	lef = chain(lef), rig = chain(rig);
	vector<int> ret = lef;
	for (int i = 1;i < rig.size();i++) ret.push_back(rig[i]);
	return ret;
}
int ti = 0;
void dfs(int n, int par) {
	ord[ti++] = n;	
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
		}
	}
}
int tot;
int search(int x) {
	ti = 0;
	dfs(vert[0], -1);
	int low = 0, up = ti;
	//pary(ord, ord + ti);
	while (low + 1< up) {
		int mid = (low + up) / 2;
		for (int i = 0;i < ti;i++) que[ord[i]] = 1;
		for (int i = mid;i < ti;i++) que[ord[i]] = 0;
		if (query(x, vert[0])) up = mid;
		else low = mid;
	}
	return ord[low];
}
void getpath(vector<int> cand, vector<int> & ret, int x, int y) {
	if (cand.size() == 0) return;
	for (int i:cand) que[i] = 0; 
	bool res = query(x, y);
	if (res) {
		return;
	} else {
		for (int i:cand) que[i] = 1;
		if (cand.size() == 1) {
			ret.push_back(cand[0]);
			return;
		} else {
			vector<int> lef, rig;
			for (int i = 0;i < cand.size();i++) {
				if (i < cand.size() / 2) lef.push_back(cand[i]);
				else rig.push_back(cand[i]);
			}
			getpath(lef, ret, x, y), getpath(rig, ret, x, y);
		}
	}
}
void Detect(int T, int N) {
	tot = N;
	if (T == 1) {
		for (int i = 0;i < N;i++) {
			for (int j = i + 1;j < N;j++) {
				que[i] = 1, que[j] = 1;
				if (query(i, j)) Answer(i, j);
				que[i] = 0, que[j] = 0;
			}
		}
		return;
	}
	srand(time(NULL));
	for (int i = 0;i < N;i++) vert.push_back(i);
	random_shuffle(vert.begin(), vert.end());
	found[vert[0]] = 1;
	for (int i = 1;i < N;i++) {
		if (found[vert[i]]) continue;
		for (int j = 0;j < N;j++) que[j] = 1;
		int anc = search(vert[i]);	
		for (int j = 0;j < N;j++) que[j] = 1;
		vector<int> cand, path;
		for (int j = 0;j < N;j++) {
			if (!found[vert[j]] && j != i) cand.push_back(vert[j]);
		}
		path.push_back(vert[i]);
		getpath(cand, path, vert[i], anc);
		path.push_back(anc);
		path = chain(path);
		for (int j:path) found[j] = 1;
		for (int j = 0;j < path.size() - 1;j++) {
			ed.push_back({path[j], path[j + 1]});
			adj[path[j]].push_back(path[j + 1]);
			adj[path[j + 1]].push_back(path[j]);
		}	
	}
	/*
	ti = 0;
	dfs(vert[0], -1);
	vector<int> rev;
	for (int i = 0;i < N;i++) rev.push_back(ord[i]);
	reverse(rev.begin(), rev.end());
	for (int i = 0;i < N - 1;i++) {
		vector<int> sub;
		for (int j = i + 1;j < N;j++) {
			sub.push_back(ord[j]);
		}	
		solve(rev[i], sub);
	}
	*/
	//assert(ed.size() == N - 1);
	for (auto i:ed) {
		if (i.ff > i.ss) swap(i.ff, i.ss);
		Answer(i.ff, i.ss);
	}
}
/*

4
10 9
0 1
0 2
1 3
2 4
1 5
2 6
2 7
7 8
5 9

4
8 7
0 1
0 2
0 3
0 4
0 5
0 6
0 7
*/

Compilation message

park.cpp: In function 'std::vector<int> chain(std::vector<int>)':
park.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 1;i < v.size() - 1;i++) {
      |                 ~~^~~~~~~~~~~~~~
park.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 1;i < rig.size();i++) ret.push_back(rig[i]);
      |                 ~~^~~~~~~~~~~~
park.cpp: In function 'void getpath(std::vector<int>, std::vector<int>&, int, int)':
park.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for (int i = 0;i < cand.size();i++) {
      |                   ~~^~~~~~~~~~~~~
park.cpp:96:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     if (i < cand.size() / 2) lef.push_back(cand[i]);
      |         ~~^~~~~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int j = 0;j < path.size() - 1;j++) {
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 8 ms 364 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 360 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 568 KB Output is correct
2 Correct 60 ms 580 KB Output is correct
3 Correct 71 ms 508 KB Output is correct
4 Correct 142 ms 528 KB Output is correct
5 Correct 114 ms 580 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 556 KB Output is correct
2 Correct 297 ms 556 KB Output is correct
3 Correct 271 ms 600 KB Output is correct
4 Correct 281 ms 624 KB Output is correct
5 Correct 272 ms 488 KB Output is correct
6 Correct 262 ms 560 KB Output is correct
7 Correct 276 ms 484 KB Output is correct
8 Correct 285 ms 556 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 480 KB Output is correct
2 Correct 269 ms 564 KB Output is correct
3 Correct 267 ms 564 KB Output is correct
4 Correct 224 ms 492 KB Output is correct
5 Correct 215 ms 548 KB Output is correct
6 Correct 146 ms 548 KB Output is correct
7 Correct 164 ms 584 KB Output is correct
8 Correct 251 ms 484 KB Output is correct
9 Correct 209 ms 460 KB Output is correct
10 Correct 207 ms 588 KB Output is correct
11 Correct 212 ms 628 KB Output is correct
12 Correct 250 ms 576 KB Output is correct
13 Correct 166 ms 620 KB Output is correct
14 Correct 267 ms 528 KB Output is correct
15 Correct 156 ms 516 KB Output is correct
16 Correct 251 ms 612 KB Output is correct
17 Correct 119 ms 544 KB Output is correct
18 Correct 227 ms 588 KB Output is correct
19 Correct 160 ms 576 KB Output is correct
20 Correct 243 ms 460 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 580 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -