oj.uz

Submission #150136

# Submission time Handle Problem Language Result Execution time Memory
150136 2019-09-01T07:47:11 Z ummm(#3574, cerberus, aayush9, knandy) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 4271 ms 488932 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;
	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 3497 ms 488932 KB Output is correct
2 Correct 3751 ms 488932 KB Output is correct
3 Correct 3810 ms 488672 KB Output is correct
4 Correct 3783 ms 488928 KB Output is correct
5 Correct 3544 ms 488928 KB Output is correct
6 Correct 4271 ms 488928 KB Output is correct
7 Correct 3678 ms 488928 KB Output is correct
8 Correct 3461 ms 488932 KB Output is correct
9 Correct 3576 ms 488932 KB Output is correct
10 Correct 3905 ms 488928 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7296 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 3497 ms 488932 KB Output is correct
4 Correct 3751 ms 488932 KB Output is correct
5 Correct 3810 ms 488672 KB Output is correct
6 Correct 3783 ms 488928 KB Output is correct
7 Correct 3544 ms 488928 KB Output is correct
8 Correct 4271 ms 488928 KB Output is correct
9 Correct 3678 ms 488928 KB Output is correct
10 Correct 3461 ms 488932 KB Output is correct
11 Correct 3576 ms 488932 KB Output is correct
12 Correct 3905 ms 488928 KB Output is correct
13 Incorrect 409 ms 486368 KB Output isn't correct
14 Halted 0 ms 0 KB -