oj.uz

Submission #151062

# Submission time Handle Problem Language Result Execution time Memory
151062 2019-09-01T16:20:43 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 497892 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];
		}
		uf[y]=x;
		for(auto i:who[y])
			who[x].push_back({i.first,time});
		who[y].clear();
		// if(merge){
		// 	function<void(int)> dfs = [&](int y){
		// 		for(auto i:who[y])
		// 			who[x].push_back({i.first, time});
		// 		for(auto i:adj[y])
		// 			dfs(i);
		// 		who[y].clear();
		// 		si[y] = 0;
		// 		adj[y].clear();
		// 	};
		// 	dfs(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 3151 ms 488932 KB Output is correct
2 Correct 3151 ms 488904 KB Output is correct
3 Correct 3186 ms 488800 KB Output is correct
4 Correct 3204 ms 488912 KB Output is correct
5 Correct 3249 ms 488816 KB Output is correct
6 Correct 3224 ms 488800 KB Output is correct
7 Correct 3171 ms 488880 KB Output is correct
8 Correct 3173 ms 488996 KB Output is correct
9 Correct 3202 ms 488888 KB Output is correct
10 Correct 3192 ms 488800 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 621 ms 497348 KB Output is correct
4 Correct 1123 ms 497172 KB Output is correct
5 Correct 2105 ms 497404 KB Output is correct
6 Correct 3777 ms 497632 KB Output is correct
7 Execution timed out 5089 ms 497892 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 3151 ms 488932 KB Output is correct
4 Correct 3151 ms 488904 KB Output is correct
5 Correct 3186 ms 488800 KB Output is correct
6 Correct 3204 ms 488912 KB Output is correct
7 Correct 3249 ms 488816 KB Output is correct
8 Correct 3224 ms 488800 KB Output is correct
9 Correct 3171 ms 488880 KB Output is correct
10 Correct 3173 ms 488996 KB Output is correct
11 Correct 3202 ms 488888 KB Output is correct
12 Correct 3192 ms 488800 KB Output is correct
13 Correct 621 ms 497348 KB Output is correct
14 Correct 1123 ms 497172 KB Output is correct
15 Correct 2105 ms 497404 KB Output is correct
16 Correct 3777 ms 497632 KB Output is correct
17 Execution timed out 5089 ms 497892 KB Time limit exceeded
18 Halted 0 ms 0 KB -