oj.uz

Submission #151064

# Submission time Handle Problem Language Result Execution time Memory
151064 2019-09-01T16:28:21 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 3353 ms 496464 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 UnionFindFinches{
	int n;
	vector<int> si,uf;
	vector<vector<pair<int,int>>> who;
	vector<vector<int>> adj;
	UnionFindFinches(int n=0):n(n),si(n,1),uf(n),who(n),adj(n){
		for(int i=0;i<n;++i) uf[i]=i;
		for(int i=0;i<n;++i) who[i].push_back({i,-1});
	}
	int find(int x){return x==uf[x]?x:find(uf[x]);}
	void join(int x, int y, int time, bool merge){
		if((x=find(x))==(y=find(y))) return;
		if(!merge){
			if(si[x]<si[y]) swap(x,y);
			si[x]+=si[y];
		}

		function<void(int,int)> dfs = [&](int x, int y){
			for(auto i:who[y])
				who[x].push_back({i.first, time});
			for(auto i:adj[y]) dfs(x, i);
			who[y].clear();
			si[y] = 0;
			adj[y].clear();
		};

		uf[y]=x;

		if(merge)
			dfs(x, y);
		else
			adj[x].push_back(y);
	}
	~UnionFindFinches(){}
};
 
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);
	}
 
	for(int finch=0;finch<K;++finch) if(pos[finch].size() >= GAP){
		UnionFindFinches dsu(N);
		for(auto i:pos[finch]) dsu.join(pos[finch][0], i, -1, 1);
 
		for(int i=0;i<M;++i){
			int x, y; tie(x,y) = edges[i];
			if(F[x] == finch && F[y] == finch) continue;
			if(F[y] == finch) swap(x,y);
			dsu.join(x,y,i, F[x] == finch);
		}
		for(auto i:dsu.who[pos[finch][0]]){
			memo[finch][F[i.first]] = max(memo[finch][F[i.first]], M - i.second);
		}
	}
}
 
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 3081 ms 488792 KB Output is correct
2 Correct 3140 ms 488800 KB Output is correct
3 Correct 3034 ms 488836 KB Output is correct
4 Correct 3353 ms 488792 KB Output is correct
5 Correct 3049 ms 488872 KB Output is correct
6 Correct 3049 ms 489028 KB Output is correct
7 Correct 3154 ms 488968 KB Output is correct
8 Correct 3060 ms 488956 KB Output is correct
9 Correct 2915 ms 488880 KB Output is correct
10 Correct 3095 ms 488772 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7416 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 616 ms 496388 KB Output is correct
4 Correct 907 ms 496304 KB Output is correct
5 Correct 1561 ms 496464 KB Output is correct
6 Incorrect 2941 ms 496420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7416 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 3081 ms 488792 KB Output is correct
4 Correct 3140 ms 488800 KB Output is correct
5 Correct 3034 ms 488836 KB Output is correct
6 Correct 3353 ms 488792 KB Output is correct
7 Correct 3049 ms 488872 KB Output is correct
8 Correct 3049 ms 489028 KB Output is correct
9 Correct 3154 ms 488968 KB Output is correct
10 Correct 3060 ms 488956 KB Output is correct
11 Correct 2915 ms 488880 KB Output is correct
12 Correct 3095 ms 488772 KB Output is correct
13 Correct 616 ms 496388 KB Output is correct
14 Correct 907 ms 496304 KB Output is correct
15 Correct 1561 ms 496464 KB Output is correct
16 Incorrect 2941 ms 496420 KB Output isn't correct
17 Halted 0 ms 0 KB -