oj.uz

Submission #150093

# Submission time Handle Problem Language Result Execution time Memory
150093 2019-09-01T07:42:18 Z ummm(#3574, cerberus, aayush9, knandy) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 508520 KB 
#include "island.h"

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

const int MAX_M = 300000;
const int GAP = 480;

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

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

map<int,int> memo[100005];
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;
	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 3577 ms 508516 KB Output is correct
2 Correct 3690 ms 508384 KB Output is correct
3 Correct 3626 ms 508516 KB Output is correct
4 Correct 3924 ms 508512 KB Output is correct
5 Correct 4438 ms 508384 KB Output is correct
6 Correct 3774 ms 508388 KB Output is correct
7 Correct 3477 ms 508388 KB Output is correct
8 Correct 4426 ms 508516 KB Output is correct
9 Correct 3742 ms 508520 KB Output is correct
10 Correct 3536 ms 508516 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Execution timed out 5124 ms 505956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 3577 ms 508516 KB Output is correct
4 Correct 3690 ms 508384 KB Output is correct
5 Correct 3626 ms 508516 KB Output is correct
6 Correct 3924 ms 508512 KB Output is correct
7 Correct 4438 ms 508384 KB Output is correct
8 Correct 3774 ms 508388 KB Output is correct
9 Correct 3477 ms 508388 KB Output is correct
10 Correct 4426 ms 508516 KB Output is correct
11 Correct 3742 ms 508520 KB Output is correct
12 Correct 3536 ms 508516 KB Output is correct
13 Execution timed out 5124 ms 505956 KB Time limit exceeded
14 Halted 0 ms 0 KB -