oj.uz

Submission #151070

# Submission time Handle Problem Language Result Execution time Memory
151070 2019-09-01T16:49:11 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 497464 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 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);
		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);
		dsu.who[pos[finch][0]].reserve(N+1);

		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,i,pos[finch][0]);
		}

		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 3113 ms 488932 KB Output is correct
2 Correct 2987 ms 488788 KB Output is correct
3 Correct 3043 ms 488800 KB Output is correct
4 Correct 3040 ms 488928 KB Output is correct
5 Correct 3127 ms 488984 KB Output is correct
6 Correct 3053 ms 488900 KB Output is correct
7 Correct 3051 ms 488876 KB Output is correct
8 Correct 3040 ms 488788 KB Output is correct
9 Correct 3027 ms 488980 KB Output is correct
10 Correct 3087 ms 488964 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7420 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 590 ms 495988 KB Output is correct
4 Correct 906 ms 496888 KB Output is correct
5 Correct 1503 ms 496796 KB Output is correct
6 Correct 2875 ms 497136 KB Output is correct
7 Execution timed out 5096 ms 497464 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 7420 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 3113 ms 488932 KB Output is correct
4 Correct 2987 ms 488788 KB Output is correct
5 Correct 3043 ms 488800 KB Output is correct
6 Correct 3040 ms 488928 KB Output is correct
7 Correct 3127 ms 488984 KB Output is correct
8 Correct 3053 ms 488900 KB Output is correct
9 Correct 3051 ms 488876 KB Output is correct
10 Correct 3040 ms 488788 KB Output is correct
11 Correct 3027 ms 488980 KB Output is correct
12 Correct 3087 ms 488964 KB Output is correct
13 Correct 590 ms 495988 KB Output is correct
14 Correct 906 ms 496888 KB Output is correct
15 Correct 1503 ms 496796 KB Output is correct
16 Correct 2875 ms 497136 KB Output is correct
17 Execution timed out 5096 ms 497464 KB Time limit exceeded
18 Halted 0 ms 0 KB -