oj.uz

Submission #150514

# Submission time Handle Problem Language Result Execution time Memory
150514 2019-09-01T08:33:58 Z ummm(#3574, cerberus, aayush9, knandy) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 4676 ms 522956 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);

	while(UF[bucket].find(pos[A][0]) == UF[bucket].find(pos[B][0])){
		UF[bucket--].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);
	}

	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 3522 ms 488928 KB Output is correct
2 Correct 3965 ms 488932 KB Output is correct
3 Correct 4676 ms 488928 KB Output is correct
4 Correct 3540 ms 488936 KB Output is correct
5 Correct 3766 ms 488928 KB Output is correct
6 Correct 3691 ms 488928 KB Output is correct
7 Correct 3620 ms 488672 KB Output is correct
8 Correct 4198 ms 488928 KB Output is correct
9 Correct 3537 ms 488932 KB Output is correct
10 Correct 3691 ms 488928 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7296 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Incorrect 858 ms 522956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7296 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 3522 ms 488928 KB Output is correct
4 Correct 3965 ms 488932 KB Output is correct
5 Correct 4676 ms 488928 KB Output is correct
6 Correct 3540 ms 488936 KB Output is correct
7 Correct 3766 ms 488928 KB Output is correct
8 Correct 3691 ms 488928 KB Output is correct
9 Correct 3620 ms 488672 KB Output is correct
10 Correct 4198 ms 488928 KB Output is correct
11 Correct 3537 ms 488932 KB Output is correct
12 Correct 3691 ms 488928 KB Output is correct
13 Incorrect 858 ms 522956 KB Output isn't correct
14 Halted 0 ms 0 KB -