oj.uz

Submission #151003

# Submission time Handle Problem Language Result Execution time Memory
151003 2019-09-01T14:21:36 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 493176 KB 
#include "island.h"

#include <bits/stdc++.h>
using namespace std;

const int MAX_M = 300000;
const int GAP = 500;

struct UnionFind {
	int n;
	vector<int> uf,si,c;
	UnionFind(int n=0):n(n),uf(n),si(n,1){
		for(int i=0;i<n;++i) 
			uf[i]=i;
	}
	int find(int x){return x==uf[x]?x:find(uf[x]);}
	bool join(int x, int y, bool keep_track = 1){
		if((x=find(x))==(y=find(y))) return false;
		if(si[x]<si[y]) swap(x,y);
		si[x]+=si[y];uf[y]=x;
		if(keep_track) c.push_back(y);
		return true;
	}
	void rollback(){
		while(c.size()){
			int x=c.back(); c.pop_back();
			si[uf[x]]-=si[x];uf[x]=x;;
		}
	}
} UF[603];

vector<pair<int,int>> edges;
vector<int> pos[100005];

int M, N;

map<int,int> memo[100005];

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
	N = F.size();
	M = S.size();

	edges.resize(M);
	for(int i=0;i<N;++i) memo[i].clear();
	for(int i=0;i<K;++i) pos[i].clear();

	for(int i=0;i<M;++i) edges[M-i-1] = {S[i], E[i]};

	for(int i=0;i<(int)F.size();++i)
		pos[F[i]].push_back(i);

	UnionFind cur(N);

	for(int i=0;i<M;++i){
		if(i%GAP==0) UF[i/GAP] = cur;
		cur.join(edges[i].first, edges[i].second, 0);
	}
}

int Separate(int A, int B){
	if(A>B) swap(A,B);
	if(memo[A].count(B)) return memo[A][B];

	int bucket = 0, ans = -1;

	int lo = 0, hi = (M-1)/GAP;
	while(lo<hi){
		int b = (lo + hi + 1)/2;

		if(UF[b].uf.size()==0) while(1);

		for(auto i:pos[A]) UF[b].join(pos[A][0], i, 1);
		for(auto i:pos[B]) UF[b].join(pos[B][0], i, 1);

		if(UF[b].find(pos[A][0]) == UF[b].find(pos[B][0])){
			hi = b - 1;
		}
		else{
			bucket = b;
			lo = b;
		}
		UF[b].rollback();
	}

	for(auto i:pos[A]) UF[bucket].join(pos[A][0], i, 1);
	for(auto i:pos[B]) UF[bucket].join(pos[B][0], i, 1);

	int start = bucket * GAP;

	for(int i=start;i<=start+GAP && i<M; ++i){
		UF[bucket].join(edges[i].first, edges[i].second, 1);
		if(UF[bucket].find(pos[A][0]) == UF[bucket].find(pos[B][0])){
			ans = M - i;
			break;
		}
	}
	assert(ans != -1);
	UF[bucket].rollback();
	return memo[A][B] = ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3074 ms 490936 KB Output is correct
2 Correct 3063 ms 492168 KB Output is correct
3 Correct 3040 ms 491900 KB Output is correct
4 Correct 3139 ms 492612 KB Output is correct
5 Correct 3101 ms 491928 KB Output is correct
6 Correct 3058 ms 491848 KB Output is correct
7 Correct 3102 ms 493032 KB Output is correct
8 Correct 3188 ms 493028 KB Output is correct
9 Correct 3083 ms 493176 KB Output is correct
10 Correct 3118 ms 493104 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 549 ms 487656 KB Output is correct
4 Correct 790 ms 490212 KB Output is correct
5 Correct 1293 ms 489952 KB Output is correct
6 Correct 2413 ms 489568 KB Output is correct
7 Correct 4937 ms 489040 KB Output is correct
8 Execution timed out 5086 ms 490416 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 3074 ms 490936 KB Output is correct
4 Correct 3063 ms 492168 KB Output is correct
5 Correct 3040 ms 491900 KB Output is correct
6 Correct 3139 ms 492612 KB Output is correct
7 Correct 3101 ms 491928 KB Output is correct
8 Correct 3058 ms 491848 KB Output is correct
9 Correct 3102 ms 493032 KB Output is correct
10 Correct 3188 ms 493028 KB Output is correct
11 Correct 3083 ms 493176 KB Output is correct
12 Correct 3118 ms 493104 KB Output is correct
13 Correct 549 ms 487656 KB Output is correct
14 Correct 790 ms 490212 KB Output is correct
15 Correct 1293 ms 489952 KB Output is correct
16 Correct 2413 ms 489568 KB Output is correct
17 Correct 4937 ms 489040 KB Output is correct
18 Execution timed out 5086 ms 490416 KB Time limit exceeded
19 Halted 0 ms 0 KB -