oj.uz

Submission #151084

# Submission time Handle Problem Language Result Execution time Memory
151084 2019-09-01T17:08:01 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 493188 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>>> adj;
	UnionFindFinches(int n=0):n(n),si(n,1),uf(n),adj(n){
		for(int i=0;i<n;++i) uf[i]=i;
	}
	int find(int x){
		if(x==uf[x]) return x;
		return find(uf[x]);
	}
	void join(int x, int y, int time, int special){
		if((x=find(x))==(y=find(y))) return;
		
		// if(x != special){
			if(si[x]<si[y]) swap(x,y);
			si[x]+=si[y];
		// }

		uf[y]=x;

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

		adj[x].push_back({y,time});
		adj[y].push_back({x,time});
		// if(x == special) dfs(x, y);
	}
};
 
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, pos[finch][0]);
 
		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,M - i,pos[finch][0]);
		}


		function<void(int,int,int)> dfs = [&](int y, int dad, int min_so_far){
			memo[finch][F[y]] = max(memo[finch][F[y]], min_so_far);
			for(auto i:dsu.adj[y]) if(i.first != dad) dfs(i.first, y, min(min_so_far,i.second));
		};
		for(auto i:dsu.adj[pos[finch][0]])
			dfs(i.first, -1, i.second);
		// for(auto i:dsu.who[pos[finch][0]])
		// 	memo[finch][F[i.first]] = max(memo[finch][F[i.first]], 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 2988 ms 489008 KB Output is correct
2 Correct 3050 ms 488888 KB Output is correct
3 Correct 3051 ms 488900 KB Output is correct
4 Correct 3390 ms 488880 KB Output is correct
5 Correct 2992 ms 488896 KB Output is correct
6 Correct 3068 ms 488804 KB Output is correct
7 Correct 3097 ms 488892 KB Output is correct
8 Correct 3124 ms 488948 KB Output is correct
9 Correct 2993 ms 488928 KB Output is correct
10 Correct 3019 ms 488884 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 Execution timed out 5130 ms 493188 KB Time limit exceeded
4 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 2988 ms 489008 KB Output is correct
4 Correct 3050 ms 488888 KB Output is correct
5 Correct 3051 ms 488900 KB Output is correct
6 Correct 3390 ms 488880 KB Output is correct
7 Correct 2992 ms 488896 KB Output is correct
8 Correct 3068 ms 488804 KB Output is correct
9 Correct 3097 ms 488892 KB Output is correct
10 Correct 3124 ms 488948 KB Output is correct
11 Correct 2993 ms 488928 KB Output is correct
12 Correct 3019 ms 488884 KB Output is correct
13 Execution timed out 5130 ms 493188 KB Time limit exceeded
14 Halted 0 ms 0 KB -