oj.uz

Submission #150996

# Submission time Handle Problem Language Result Execution time Memory
150996 2019-09-01T14:10:01 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 524288 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[MAX_M/GAP+2];

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;

	for(int i=0;i<M;i+=GAP){
		if(UF[i/GAP].find(pos[A][0]) == UF[i/GAP].find(pos[B][0]))
			break;
		bucket = i/GAP;
	}

	while(1){
		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);

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

	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 3855 ms 490976 KB Output is correct
2 Correct 3768 ms 491680 KB Output is correct
3 Correct 3769 ms 491608 KB Output is correct
4 Correct 3765 ms 491804 KB Output is correct
5 Correct 3631 ms 491384 KB Output is correct
6 Correct 3671 ms 491540 KB Output is correct
7 Correct 3743 ms 491536 KB Output is correct
8 Correct 3780 ms 491596 KB Output is correct
9 Correct 3605 ms 491620 KB Output is correct
10 Correct 3667 ms 491224 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 1085 ms 524288 KB Output is correct
4 Execution timed out 5077 ms 499352 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 3855 ms 490976 KB Output is correct
4 Correct 3768 ms 491680 KB Output is correct
5 Correct 3769 ms 491608 KB Output is correct
6 Correct 3765 ms 491804 KB Output is correct
7 Correct 3631 ms 491384 KB Output is correct
8 Correct 3671 ms 491540 KB Output is correct
9 Correct 3743 ms 491536 KB Output is correct
10 Correct 3780 ms 491596 KB Output is correct
11 Correct 3605 ms 491620 KB Output is correct
12 Correct 3667 ms 491224 KB Output is correct
13 Correct 1085 ms 524288 KB Output is correct
14 Execution timed out 5077 ms 499352 KB Time limit exceeded
15 Halted 0 ms 0 KB -