oj.uz

Submission #430867

# Submission time Handle Problem Language Result Execution time Memory
430867 2021-06-17T07:15:10 Z 8e7 Park (JOI17_park) C++14
77 / 100
 171 ms 644 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] = 0;
		vector<int> cand, path;
		for (int j = 0;j < N;j++) {
			if (!found[vert[j]] && j != i) cand.push_back(vert[j]), que[vert[j]] = 1;
		}
		que[vert[i]] = 1, que[anc] = 1;
		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:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for (int j = 0;j < path.size() - 1;j++) {
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 11 ms 356 KB Output is correct
3 Correct 10 ms 332 KB Output is correct
4 Correct 10 ms 332 KB Output is correct
5 Correct 11 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 460 KB Output is correct
2 Correct 44 ms 536 KB Output is correct
3 Correct 58 ms 528 KB Output is correct
4 Correct 87 ms 508 KB Output is correct
5 Correct 72 ms 484 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 552 KB Output is correct
2 Correct 150 ms 528 KB Output is correct
3 Correct 171 ms 512 KB Output is correct
4 Correct 160 ms 612 KB Output is correct
5 Correct 136 ms 560 KB Output is correct
6 Correct 170 ms 488 KB Output is correct
7 Correct 142 ms 644 KB Output is correct
8 Correct 147 ms 532 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 492 KB Output is correct
2 Correct 156 ms 492 KB Output is correct
3 Correct 131 ms 536 KB Output is correct
4 Correct 100 ms 480 KB Output is correct
5 Correct 114 ms 472 KB Output is correct
6 Correct 110 ms 580 KB Output is correct
7 Correct 86 ms 516 KB Output is correct
8 Correct 117 ms 524 KB Output is correct
9 Correct 108 ms 532 KB Output is correct
10 Correct 123 ms 580 KB Output is correct
11 Correct 144 ms 580 KB Output is correct
12 Correct 162 ms 536 KB Output is correct
13 Correct 84 ms 496 KB Output is correct
14 Correct 144 ms 552 KB Output is correct
15 Correct 84 ms 460 KB Output is correct
16 Correct 151 ms 612 KB Output is correct
17 Correct 67 ms 508 KB Output is correct
18 Correct 140 ms 484 KB Output is correct
19 Correct 80 ms 636 KB Output is correct
20 Correct 131 ms 568 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 564 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -