oj.uz

Submission #151041

# Submission time Handle Problem Language Result Execution time Memory
151041 2019-09-01T15:24:10 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 498232 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[603];

struct UnionFindPathCompression {
	int n;
	vector<int> uf;
	UnionFindPathCompression(int n=0):n(n),uf(n){
		for(int i=0;i<n;++i) uf[i]=i;
	}
	int find(int x){return uf[x] = x==uf[x]?x:find(uf[x]);}
	void join(int x, int y){
		if((x=find(x))==(y=find(y))) return;
		uf[y]=x;
	}
};

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


	vector<pair<int,int>> queries;
	for(int finch=0;finch<K;++finch) if(pos[finch].size() >= GAP)
		for(int i=finch+1;i<K;++i) queries.push_back({finch,i});
	
	int Q = queries.size();
	
	vector<int> lo(Q,0), hi(Q,M-1);

	for(int iter=19;iter--;){

		vector<vector<int>> mid(M);
		for(auto i=0;i<Q;++i)
			mid[(lo[i]+hi[i])/2].push_back(i);

		UnionFind dsu(N);
		for(int i=0;i<M;++i){
			dsu.join(edges[i].first, edges[i].second, 0);
			for(auto j:mid[i]){
				int A = queries[j].first, B = queries[j].second;
				
				for(auto i:pos[A]) dsu.join(pos[A][0], i, 1);
				for(auto i:pos[B]) dsu.join(pos[B][0], i, 1);

				if(dsu.find(pos[A][0]) == dsu.find(pos[B][0]))
					hi[j] = i;
				else
					lo[j] = i + 1;

				dsu.rollback();
			}
		}
	}

	for(int i=0;i<Q;++i){
		// cout << queries[i].first << ' ' << queries[i].second << ' ' << M - hi[i] << '\n';
		memo[queries[i].first][queries[i].second] = max(memo[queries[i].first][queries[i].second], M - hi[i]);
	}
}

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;

	int lo = 0, hi = (M-1)/GAP;
	while(lo<hi){
		int b = (lo + hi + 1)/2;

		for(auto i:pos[A]) UF[b].join(pos[A][0], i, 1);
		for(auto i:pos[B]) UF[b].join(pos[B][0], i, 1);

		if(UF[b].find(pos[A][0]) == UF[b].find(pos[B][0])){
			hi = b - 1;
		}
		else{
			lo = b;
		}
		UF[b].rollback();
	}

	bucket = lo;

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

	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;
		}
	}
	UF[bucket].rollback();
	return memo[A][B] = ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3333 ms 496732 KB Output is correct
2 Correct 3423 ms 496732 KB Output is correct
3 Correct 3426 ms 496792 KB Output is correct
4 Correct 3414 ms 496844 KB Output is correct
5 Correct 3428 ms 496844 KB Output is correct
6 Correct 3529 ms 496616 KB Output is correct
7 Correct 3497 ms 496864 KB Output is correct
8 Correct 3487 ms 496792 KB Output is correct
9 Correct 3475 ms 496652 KB Output is correct
10 Correct 3563 ms 496704 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 Correct 901 ms 495168 KB Output is correct
4 Correct 1247 ms 498196 KB Output is correct
5 Correct 2029 ms 497912 KB Output is correct
6 Correct 3617 ms 498156 KB Output is correct
7 Execution timed out 5082 ms 498232 KB Time limit exceeded
8 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 3333 ms 496732 KB Output is correct
4 Correct 3423 ms 496732 KB Output is correct
5 Correct 3426 ms 496792 KB Output is correct
6 Correct 3414 ms 496844 KB Output is correct
7 Correct 3428 ms 496844 KB Output is correct
8 Correct 3529 ms 496616 KB Output is correct
9 Correct 3497 ms 496864 KB Output is correct
10 Correct 3487 ms 496792 KB Output is correct
11 Correct 3475 ms 496652 KB Output is correct
12 Correct 3563 ms 496704 KB Output is correct
13 Correct 901 ms 495168 KB Output is correct
14 Correct 1247 ms 498196 KB Output is correct
15 Correct 2029 ms 497912 KB Output is correct
16 Correct 3617 ms 498156 KB Output is correct
17 Execution timed out 5082 ms 498232 KB Time limit exceeded
18 Halted 0 ms 0 KB -