oj.uz

Submission #150985

# Submission time Handle Problem Language Result Execution time Memory
150985 2019-09-01T13:57:31 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 3815 ms 493140 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, start = 0, ans = -1;

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

	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);

	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 3739 ms 493140 KB Output is correct
2 Correct 3782 ms 493048 KB Output is correct
3 Correct 3747 ms 493104 KB Output is correct
4 Correct 3676 ms 493064 KB Output is correct
5 Correct 3777 ms 493040 KB Output is correct
6 Correct 3684 ms 493028 KB Output is correct
7 Correct 3677 ms 493096 KB Output is correct
8 Correct 3726 ms 493092 KB Output is correct
9 Correct 3815 ms 493076 KB Output is correct
10 Correct 3775 ms 493120 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 Incorrect 526 ms 488684 KB Output isn't correct
4 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 3739 ms 493140 KB Output is correct
4 Correct 3782 ms 493048 KB Output is correct
5 Correct 3747 ms 493104 KB Output is correct
6 Correct 3676 ms 493064 KB Output is correct
7 Correct 3777 ms 493040 KB Output is correct
8 Correct 3684 ms 493028 KB Output is correct
9 Correct 3677 ms 493096 KB Output is correct
10 Correct 3726 ms 493092 KB Output is correct
11 Correct 3815 ms 493076 KB Output is correct
12 Correct 3775 ms 493120 KB Output is correct
13 Incorrect 526 ms 488684 KB Output isn't correct
14 Halted 0 ms 0 KB -