oj.uz

Submission #151079

# Submission time Handle Problem Language Result Execution time Memory
151079 2019-09-01T17:04:11 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 491692 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});
		// 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)> dfs = [&](int y, int min_so_far){
			memo[finch][F[y]] = max(memo[finch][F[y]], min_so_far);
			for(auto i:dsu.adj[y]) dfs(i.first, min(min_so_far,i.second));
		};
		for(auto i:dsu.adj[pos[finch][0]])
			dfs(i.first, 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 3138 ms 488800 KB Output is correct
2 Correct 2969 ms 488800 KB Output is correct
3 Correct 2987 ms 488852 KB Output is correct
4 Correct 3041 ms 488848 KB Output is correct
5 Correct 3061 ms 488964 KB Output is correct
6 Correct 3005 ms 489060 KB Output is correct
7 Correct 2882 ms 488832 KB Output is correct
8 Correct 2960 ms 488884 KB Output is correct
9 Correct 3087 ms 488932 KB Output is correct
10 Correct 3224 ms 489036 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 564 ms 490700 KB Output is correct
4 Correct 710 ms 491060 KB Output is correct
5 Correct 1102 ms 491304 KB Output is correct
6 Correct 2139 ms 491352 KB Output is correct
7 Execution timed out 5076 ms 491692 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 3138 ms 488800 KB Output is correct
4 Correct 2969 ms 488800 KB Output is correct
5 Correct 2987 ms 488852 KB Output is correct
6 Correct 3041 ms 488848 KB Output is correct
7 Correct 3061 ms 488964 KB Output is correct
8 Correct 3005 ms 489060 KB Output is correct
9 Correct 2882 ms 488832 KB Output is correct
10 Correct 2960 ms 488884 KB Output is correct
11 Correct 3087 ms 488932 KB Output is correct
12 Correct 3224 ms 489036 KB Output is correct
13 Correct 564 ms 490700 KB Output is correct
14 Correct 710 ms 491060 KB Output is correct
15 Correct 1102 ms 491304 KB Output is correct
16 Correct 2139 ms 491352 KB Output is correct
17 Execution timed out 5076 ms 491692 KB Time limit exceeded
18 Halted 0 ms 0 KB -