oj.uz

Submission #151068

# Submission time Handle Problem Language Result Execution time Memory
151068 2019-09-01T16:45:50 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 499216 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();
			uf[y] = x;
			si[y] = 0;
			for(auto i:adj[y]) dfs(x, i);
		};

		adj[x].push_back(y);
		for(auto i:who[y]) {
			who[x].push_back({i.first, time});
			uf[i.first] = x;
		}
		// 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 3204 ms 489012 KB Output is correct
2 Correct 3151 ms 488968 KB Output is correct
3 Correct 3145 ms 488868 KB Output is correct
4 Correct 3096 ms 488944 KB Output is correct
5 Correct 3221 ms 488860 KB Output is correct
6 Correct 3098 ms 488932 KB Output is correct
7 Correct 3051 ms 488948 KB Output is correct
8 Correct 3100 ms 488892 KB Output is correct
9 Correct 3090 ms 488788 KB Output is correct
10 Correct 3000 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 Correct 631 ms 497444 KB Output is correct
4 Correct 1052 ms 498160 KB Output is correct
5 Correct 1870 ms 498772 KB Output is correct
6 Correct 3909 ms 498928 KB Output is correct
7 Execution timed out 5047 ms 499216 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 3204 ms 489012 KB Output is correct
4 Correct 3151 ms 488968 KB Output is correct
5 Correct 3145 ms 488868 KB Output is correct
6 Correct 3096 ms 488944 KB Output is correct
7 Correct 3221 ms 488860 KB Output is correct
8 Correct 3098 ms 488932 KB Output is correct
9 Correct 3051 ms 488948 KB Output is correct
10 Correct 3100 ms 488892 KB Output is correct
11 Correct 3090 ms 488788 KB Output is correct
12 Correct 3000 ms 488884 KB Output is correct
13 Correct 631 ms 497444 KB Output is correct
14 Correct 1052 ms 498160 KB Output is correct
15 Correct 1870 ms 498772 KB Output is correct
16 Correct 3909 ms 498928 KB Output is correct
17 Execution timed out 5047 ms 499216 KB Time limit exceeded
18 Halted 0 ms 0 KB -