oj.uz

Submission #151065

# Submission time Handle Problem Language Result Execution time Memory
151065 2019-09-01T16:39:38 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 496624 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, int 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;

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

		adj[x].push_back(y);
		
		if(merge) 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);
		dsu.who[pos[finch][0]].reserve(N+1);

		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 3154 ms 488888 KB Output is correct
2 Correct 3070 ms 488784 KB Output is correct
3 Correct 3149 ms 488928 KB Output is correct
4 Correct 3146 ms 488864 KB Output is correct
5 Correct 3256 ms 488804 KB Output is correct
6 Correct 3206 ms 488932 KB Output is correct
7 Correct 3099 ms 488988 KB Output is correct
8 Correct 3178 ms 489072 KB Output is correct
9 Correct 3074 ms 488896 KB Output is correct
10 Correct 3156 ms 488944 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 5100 ms 496624 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 3154 ms 488888 KB Output is correct
4 Correct 3070 ms 488784 KB Output is correct
5 Correct 3149 ms 488928 KB Output is correct
6 Correct 3146 ms 488864 KB Output is correct
7 Correct 3256 ms 488804 KB Output is correct
8 Correct 3206 ms 488932 KB Output is correct
9 Correct 3099 ms 488988 KB Output is correct
10 Correct 3178 ms 489072 KB Output is correct
11 Correct 3074 ms 488896 KB Output is correct
12 Correct 3156 ms 488944 KB Output is correct
13 Execution timed out 5100 ms 496624 KB Time limit exceeded
14 Halted 0 ms 0 KB -