oj.uz

답안 #60429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60429 2018-07-24T07:42:55 Z 윤교준(#1744) Park (JOI17_park) C++11
77 / 100
 328 ms 2008 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 int O[MAXN], RO[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;
		} else {
			EV.eb(s, e);
			fg(GV, s, e);
		}
		if(s) V.eb(s);
		if(e) 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 void dfs(int i, int &c) {
	c++; O[i] = c;
	for(int v : GV[i]) if(!O[v]) dfs(v, c);
}

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);
		sorv(V); univ(V);

		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("");
		}

		fill(O, O+N+1, 0);
		int cnt = 0; dfs(0, cnt);
		for(int v : G) RO[O[v]] = v;

		{
			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, ri, V, false)) e = m;
				else s = m+1;
			}

			if(debug) printf("ri=%d, s=%d :: RO=%d\n", ri, s, RO[s]);

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

	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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 22 ms 620 KB Output is correct
3 Correct 17 ms 620 KB Output is correct
4 Correct 17 ms 728 KB Output is correct
5 Correct 17 ms 728 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 948 KB Output is correct
2 Correct 202 ms 948 KB Output is correct
3 Correct 248 ms 2008 KB Output is correct
4 Correct 151 ms 2008 KB Output is correct
5 Correct 185 ms 2008 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 2008 KB Output is correct
2 Correct 229 ms 2008 KB Output is correct
3 Correct 259 ms 2008 KB Output is correct
4 Correct 233 ms 2008 KB Output is correct
5 Correct 328 ms 2008 KB Output is correct
6 Correct 312 ms 2008 KB Output is correct
7 Correct 242 ms 2008 KB Output is correct
8 Correct 303 ms 2008 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 2008 KB Output is correct
2 Correct 266 ms 2008 KB Output is correct
3 Correct 297 ms 2008 KB Output is correct
4 Correct 215 ms 2008 KB Output is correct
5 Correct 247 ms 2008 KB Output is correct
6 Correct 205 ms 2008 KB Output is correct
7 Correct 173 ms 2008 KB Output is correct
8 Correct 235 ms 2008 KB Output is correct
9 Correct 227 ms 2008 KB Output is correct
10 Correct 237 ms 2008 KB Output is correct
11 Correct 243 ms 2008 KB Output is correct
12 Correct 269 ms 2008 KB Output is correct
13 Correct 191 ms 2008 KB Output is correct
14 Correct 247 ms 2008 KB Output is correct
15 Correct 236 ms 2008 KB Output is correct
16 Correct 264 ms 2008 KB Output is correct
17 Correct 164 ms 2008 KB Output is correct
18 Correct 268 ms 2008 KB Output is correct
19 Correct 177 ms 2008 KB Output is correct
20 Correct 281 ms 2008 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 283 ms 2008 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -