Submission #1022544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022544		Tob	Park (JOI17_park)	C++14	100 / 100	133 ms	3444 KiB

park

#include <bits/stdc++.h>
#include "park.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
/*
#define NMAX  1400
#define DMAX  7
#define QMAX  45000

static int T,N,M,Asktotal,Answertotal;
static int edge_list[NMAX][DMAX];
static int checked[NMAX][DMAX];
static int degree[NMAX];
static int visited[NMAX];
static void WA(int wa_num) {
	cout << "Wrong Answer " << wa_num << "\n";
	exit(0);
}
void Detect(int T, int N);

void Answer(int A, int B) {
	int i;
	if(A < 0||A >= B||B >= N) WA(1);
	for(i = 0 ; i < degree[A] ; i++) {
		if(edge_list[A][i] == B) {
			if(checked[A][i] == 1) WA(3);
			Answertotal++;
			checked[A][i] = 1;
			return;
		}
	}
	WA(2);
}
static void dfs(int now, int Place[]) {
	visited[now] = 1;
	int i;
	for(i = 0 ; i < degree[now] ; i++) {
		if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) dfs(edge_list[now][i], Place);
	}
}
int Ask(int A, int B, int Place[]) {
	int i;
	Asktotal++;
	if(Asktotal>QMAX) WA(5);
	if(A < 0||A >= B||B >= N) WA(4);
	if(Place[A] != 1) WA(4);
	if(Place[B] != 1) WA(4);
	for(i = 0 ; i < N ; i++) {
		if(Place[i]<0||Place[i]>1) WA(4);
		visited[i] = 0;
	}
	dfs(A, Place);
	return visited[B];
}*/

//-----------------------------

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int val(int x) {
	uniform_int_distribution <int> rnd(0, x-1);
	return rnd(rng);
}

static int Place[1400];
int n, tim, m;
int bio[1400], dis[1400], st[1400], en[1400], wh[1400];
bool ban[1400][1400];
vector <int> adj[1400];

void dfs(int x, int p = -1) {
	for (auto y : adj[x]) {
		if (y == p) continue;
		dis[y] = dis[x] + 1;
		dfs(y, x);
	}
}

void dfs2(int x, int p = -1) {
	wh[tim] = x;
	st[x] = tim++;
	for (auto y : adj[x]) {
		if (y == p) continue;
		dfs2(y, x);
	}
	en[x] = tim-1;
}

void ans(int x, int y) {
	if (x > y) swap(x, y);
	if (ban[x][y]) return;
	ban[x][y] = 1;
	Answer(x, y);
	m++;
	if (m >= n) return;
	adj[x].pb(y);
	adj[y].pb(x);
	bio[x] = bio[y] = 1;
}
int ask(int x, int y) {
	if (x > y) swap(x, y);
	return Ask(x, y, Place);
}

void rek(int x, int y) {
	for (int i = 0; i < n; i++) Place[i] = 0;
	Place[x] = Place[y] = 1;
	if (ask(x, y)) {
		ans(x, y);
		return;
	}
	vector <int> v;
	for (int i = 0; i < n; i++) {
		if (i == x || i == y || bio[i]) continue;
		Place[i] = 1;
		v.pb(i);
	}
	int lo = 0, hi = n-3;
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		for (int i = mid; i < v.size(); i++) Place[v[i]] = 0;
		if (ask(x, y)) hi = mid-1;
		else lo = mid;
		for (int i = mid; i < v.size(); i++) Place[v[i]] = 1;
	}
	rek(x, v[lo]);
	rek(v[lo], y);
}

void rec(int x, int y, vector <int> u) {
	if (u.empty()) return;
	for (int i = 0; i < n; i++) Place[i] = 0;
	Place[x] = 1;
	for (int i = 0; i < u.size(); i++) Place[u[i]] = 1;
	if (!ask(x, y)) return;
	int lo = 0, hi = u.size()-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		for (int i = 0; i < n; i++) Place[i] = 0;
		Place[x] = 1;
		for (int i = 0; i <= mid; i++) Place[u[i]] = 1;
		if (ask(x, y)) hi = mid;
		else lo = mid+1;
	}
	int z = u[lo];
	ans(x, z);
	for (auto it : adj[z]) {
		if (st[it] < st[z]) continue;
		vector <int> uu;
		for (int i = st[it]; i <= en[it]; i++) uu.pb(wh[i]);
		rec(x, it, uu);
	}
	vector <int> uu;
	for (auto i : u) if (st[i] < st[z] || st[i] > en[z]) uu.pb(i);
	rec(x, y, uu);
}

void Detect(int T, int N) {
	n = N;
	if (N == 2) {
		Answer(0, 1);
		return;
	}
	bio[0] = 1;
	while (1) {
		vector <int> v;
		for (int i = 0; i < n; i++) if (!bio[i]) v.pb(i);
		if (v.empty()) break;
//		shuffle(all(v), rng);
		int x = v[0];
		
		dis[0] = 0;
		dfs(0);
		int lo = 0, hi = 0;
		for (int i = 0; i < n; i++) if (bio[i]) hi = max(hi, dis[i]);
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			for (int i = 0; i < n; i++) Place[i] = (!bio[i] || dis[i] < mid);
			if (!ask(0, x)) lo = mid;
			else hi = mid-1;
		}
		int d = lo;
		if (!d) {
			rek(0, x);
			continue;
		}
		v.clear();
		for (int i = 0; i < n; i++) if (bio[i] && dis[i] == d) v.pb(i);
		lo = 0; hi = v.size()-1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			for (int i = 0; i < n; i++) Place[i] = (!bio[i] || dis[i] <= d);
			for (int i = mid+1; i < v.size(); i++) Place[v[i]] = 0;
			if (ask(0, x)) hi = mid;
			else lo = mid+1;
		}
		rek(v[lo], x);
	}
	for (int i = 0; i < n; i++) {
		for (auto x : adj[i]) {
			tim = 0;
			dfs2(x, i);
			for (auto y : adj[x]) {
				if (y == i) continue;
				vector <int> uu;
				for (int i = st[y]; i <= en[y]; i++) uu.pb(wh[i]);
				rec(i, y, uu);
			}
		}
	}
}

//-----------------------------
/*
int main(int argc, char **argv) {
	int i;
	cin >> T >> N >> M;
	Answertotal = 0;
	for(i = 0 ; i < M ; i++) {
		int ea,eb;
		cin >> ea >> eb;
		checked[ea][degree[ea]] =  0;
		checked[eb][degree[eb]] =  0;
		edge_list[ea][degree[ea]++] = eb;
		edge_list[eb][degree[eb]++] = ea;
	}
	Detect(T, N);
	if(Answertotal<M) WA(6);
	cout << "Accepted\n";
	return 0;
}*/

Compilation message (stderr)

park.cpp: In function 'void rek(int, int)':
park.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for (int i = mid; i < v.size(); i++) Place[v[i]] = 0;
      |                     ~~^~~~~~~~~~
park.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (int i = mid; i < v.size(); i++) Place[v[i]] = 1;
      |                     ~~^~~~~~~~~~
park.cpp: In function 'void rec(int, int, std::vector<int>)':
park.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 0; i < u.size(); i++) Place[u[i]] = 1;
      |                  ~~^~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:201:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |    for (int i = mid+1; i < v.size(); i++) Place[v[i]] = 0;
      |                        ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23