oj.uz

Submission #60458

# Submission time Handle Problem Language Result Execution time Memory
60458 2018-07-24T08:23:36 Z 윤교준(#1744) Park (JOI17_park) C++11
77 / 100
 643 ms 2208 KB 
#include "park.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

static const bool debug = 0;
static const int MAXN = 1405;

static int __ask[1400];

static vector<int> GV[MAXN];

static vector<pii> EV;
static vector<int> G;
static bitset<MAXN> isG;
static int N;

static bool ask(int s, int e, vector<int> &V, bool zerochk = true) {
	for(int i = 0; i < N; i++) __ask[i] = 0;
	for(int v : V) __ask[v] = 1;
	if(zerochk) {
		bool isZ = false;
		for(int v : V) if(!v) isZ = true;
		if(!s || !e) isZ = true;
		if(isZ) for(int v : G) __ask[v] = 1;
	}
	__ask[s] = __ask[e] = 1;
	if(s > e) swap(s, e);
	return Ask(s, e, __ask);
}
static bool hasEdge(int a, int b) { vector<int> V; return ask(a, b, V); }
static vector<int> add(vector<int> &A, vector<int> &B) {
	vector<int> ret = A;
	for(int v : B) ret.eb(v);
	return ret;
}

static int g(vector<int> &S, vector<int> &S3, int s, int e) {
	int n = sz(S), m = n >> 1;
	if(1 == n) return S[0];

	vector<int> S1, S2;
	for(int i = 0; i < m; i++) S1.eb(S[i]);
	for(int i = m; i < n; i++) S2.eb(S[i]);

	vector<int> T = add(S2, S3);
	if(ask(s, e, T)) {
		return g(S2, S3, s, e);
	}
	
	S2 = add(S2, S3);
	return g(S1, S2, s, e);
}

static void f(vector<int> &V, vector<int> &U, int s, int e, int &ri) {
	if(hasEdge(s, e)) {
		if(!s || !e) {
			ri = s + e;
		}
		V.eb(s);
		V.eb(e);
		return;
	}

	vector<int> S1 = U, S3;
	int x = g(S1, S3, s, e);

	S1 = add(S1, S3);
	f(V, S1, s, x, ri);
	f(V, S1, x, e, ri);
}

static bitset<MAXN> cannotGo;
static int O[MAXN], RO[MAXN];
static void dfs(vector<int> &TV, int i, int &c) {
	c++; O[i] = c; TV.eb(i);
	for(int v : GV[i]) if(!O[v] && !cannotGo[v]) dfs(TV, v, c);
}
static void putTree(vector<int> &Ans, int x, int y) {
	if(cannotGo[x] || 7 <= sz(Ans)) return;
	vector<int> TV;
	fill(O, O+N+1, 0);
	int cnt = 0;
	dfs(TV, x, cnt);
	for(int v : TV) RO[O[v]] = v;

	if(!ask(x, y, TV, false)) return;

	int s = 1, e = cnt; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V;
		for(int i = 1; i <= m; i++) V.eb(RO[i]);
		if(ask(0, y, V, false)) e = m;
		else s = m+1;
	}

	Ans.eb(RO[s]);
	cannotGo[RO[s]] = true;

	for(int v : GV[RO[s]]) {
		putTree(Ans, v, y);
	}
}

void Detect(int _T, int _N) {
	N = _N;

	if(N <= 250) {
		for(int i = 0; i < N; i++) for(int j = i+1; j < N; j++)
			if(hasEdge(i, j)) Answer(i, j);
		return;
	}

	isG[0] = true; G.eb(0);
	for(int i = 1; i < N; i++) if(!isG[i]) {
		vector<int> V, U; int ri = 0;
		for(int j = 1; j <= N; j++) if(!isG[j] && i != j) U.eb(j);
		f(V, U, 0, i, ri);

		{
			vector<int> T;
			for(int v : V) {
				if(T.empty() || T.back() != v)
					T.eb(v);
			}
			swap(V, T);
		}
		
		if(debug) {
			printf("i=%d :: %d\n", i, ri);
			printf("V : "); for(int v : V) printf("%d ", v); puts("");
			printf("U : "); for(int v : U) printf("%d ", v); puts("");
		}

		for(int i = 1, n = sz(V); i < n; i++) {
			cannotGo.reset();
			vector<int> Ans;
			putTree(Ans, 0, V[i]);

			for(int v : Ans) {
				EV.eb(v, V[i]);
				fg(GV, v, V[i]);
				G.eb(V[i]);
				isG[V[i]] = true;
			}

			if(debug) {
				printf("i=%d, v=%d :: ", i, V[i]);
				for(int v : Ans) printf("%d ", v);
				puts("");
			}
		}
	}

	for(auto &v : EV) if(v.first > v.second) swap(v.first, v.second);
	sorv(EV); univ(EV);
	for(auto &v : EV) Answer(v.first, v.second);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 22 ms 488 KB Output is correct
3 Correct 22 ms 584 KB Output is correct
4 Correct 22 ms 652 KB Output is correct
5 Correct 21 ms 652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 1340 KB Output is correct
2 Correct 262 ms 1340 KB Output is correct
3 Correct 363 ms 2208 KB Output is correct
4 Correct 490 ms 2208 KB Output is correct
5 Correct 407 ms 2208 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 2208 KB Output is correct
2 Correct 374 ms 2208 KB Output is correct
3 Correct 365 ms 2208 KB Output is correct
4 Correct 285 ms 2208 KB Output is correct
5 Correct 343 ms 2208 KB Output is correct
6 Correct 428 ms 2208 KB Output is correct
7 Correct 347 ms 2208 KB Output is correct
8 Correct 315 ms 2208 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 2208 KB Output is correct
2 Correct 386 ms 2208 KB Output is correct
3 Correct 369 ms 2208 KB Output is correct
4 Correct 380 ms 2208 KB Output is correct
5 Correct 444 ms 2208 KB Output is correct
6 Correct 378 ms 2208 KB Output is correct
7 Correct 425 ms 2208 KB Output is correct
8 Correct 424 ms 2208 KB Output is correct
9 Correct 351 ms 2208 KB Output is correct
10 Correct 402 ms 2208 KB Output is correct
11 Correct 392 ms 2208 KB Output is correct
12 Correct 359 ms 2208 KB Output is correct
13 Correct 376 ms 2208 KB Output is correct
14 Correct 369 ms 2208 KB Output is correct
15 Correct 450 ms 2208 KB Output is correct
16 Correct 348 ms 2208 KB Output is correct
17 Correct 452 ms 2208 KB Output is correct
18 Correct 440 ms 2208 KB Output is correct
19 Correct 436 ms 2208 KB Output is correct
20 Correct 452 ms 2208 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 2208 KB Output is correct
2 Incorrect 525 ms 2208 KB Wrong Answer[2]
3 Halted 0 ms 0 KB -