oj.uz

Submission #148926

# Submission time Handle Problem Language Result Execution time Memory
148926 2019-09-01T05:24:19 Z 잉여로운 고3(#3749, imyujin, sebinkim) Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 5000 ms 166496 KB 
#include "island.h"
#include <bits/stdc++.h>
using namespace std;

const int SQRTN = 320;
const int MAXN = SQRTN * SQRTN;
const int MAXM = 3000010;

struct EDGE {
	int S, E, idx;

	EDGE(int S = 0, int E = 0, int i = 0) : S(S), E(E), idx(i) {}
} ed[MAXM];

int N, M, K;
vector<int> F;
int uni[MAXN];
int mem[SQRTN][MAXN];
bool aa[MAXN], bb[MAXN];
int cnt[MAXN];

int guni(int x) { return x == uni[x] ? x : uni[x] = guni(uni[x]); }
void unite(int x, int y) { uni[guni(x)] = guni(y); }

void Init(int K, vector<int> FF, vector<int> SS, vector<int> EE){
	N = FF.size();
	M = SS.size();
	F = FF;

	for(int i = 0; i < M; i++) ed[i] = EDGE(SS[M - i - 1], EE[M - i - 1], i);
	//for(int i = 0; i < M; i++) printf("%d %d %d\n", ed[i].S, ed[i].E, ed[i].idx);

	for(int i = 0; i < N; i++) uni[i] = i;
	int nn = 0;
	for(int i = 0; i < M; i++) if(guni(ed[i].S) != guni(ed[i].E)) {
		ed[nn++] = ed[i];
		unite(ed[i].S, ed[i].E);
		//printf("%d %d %d\n", ed[i].S, ed[i].E, ed[i].idx);
		//for(int i = 0; i < N; i++) printf("%d ", guni(i));
		//printf("\n");
	}

	for(int i = 0; i < N; i++) uni[i] = i;
	for(int i = 0; i < N - 1; i++) {
		if(i % SQRTN == 0) for(int j = 0; j < N; j++) mem[i / SQRTN][j] = guni(j);
		unite(ed[i].S, ed[i].E);
	}

	for(int i = 0; i < N; i++) cnt[F[i]]++;
}

int Separate(int A, int B){
	if(cnt[A] == 0 || cnt[B] == 0) return 0;
	int s = 0, e = (N - 1) / SQRTN;
	while(s < e) {
		int m = (s + e + 1) / 2;
		for(int i = 0; i < N; i++) aa[i] = bb[i] = false;
		for(int i = 0; i < N; i++) {
			if(F[i] == A) aa[mem[m][i]] = true;
			else if(F[i] == B) bb[mem[m][i]] = true;
		}
		bool b = false;
		for(int i = 0; i < N; i++) if(aa[i] && bb[i]) b = true;
		if(b) e = m - 1;
		else s = m;
	}

	//printf("A = %d, B = %d, s = %d\n", A, B, s);

	for(int i = 0; i < N; i++) {
		uni[i] = mem[s][i];
		aa[i] = false;
		bb[i] = false;
	}
	for(int i = 0; i < N; i++) {
		if(F[i] == A) aa[uni[i]] = true;
		else if(F[i] == B) bb[uni[i]] = true;
	}
	//for(int i = 0; i < N; i++) printf("i = %d, uni = %d, %d %d\n", i, uni[i], aa[i], bb[i]);
	for(int i = s * SQRTN; ; i++) {
		aa[guni(ed[i].E)] |= aa[guni(ed[i].S)];
		bb[guni(ed[i].E)] |= bb[guni(ed[i].S)];
		unite(ed[i].S, ed[i].E);
		if(aa[guni(ed[i].E)] && bb[guni(ed[i].E)]) return M - ed[i].idx;
	}

	return 0;
}

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5098 ms 166496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Execution timed out 5109 ms 166116 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Execution timed out 5098 ms 166496 KB Time limit exceeded
4 Halted 0 ms 0 KB -