oj.uz

Submission #151061

# Submission time Handle Problem Language Result Execution time Memory
151061 2019-09-01T16:18:13 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 3349 ms 498380 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, bool 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;
		if(merge){
			function<void(int)> dfs = [&](int y){
				for(auto i:who[y])
					who[x].push_back({i.first, time});
				for(auto i:adj[y])
					dfs(i);
				who[y].clear();
				si[y] = 0;
				adj[y].clear();
			};
			dfs(y);
		}
		else
			adj[x].push_back(y);
	}
	~UnionFindFinches(){}
};
 
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, 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 3184 ms 488808 KB Output is correct
2 Correct 3108 ms 488788 KB Output is correct
3 Correct 3140 ms 488820 KB Output is correct
4 Correct 3249 ms 488800 KB Output is correct
5 Correct 3102 ms 488972 KB Output is correct
6 Correct 3270 ms 488864 KB Output is correct
7 Correct 3349 ms 488860 KB Output is correct
8 Correct 3166 ms 488800 KB Output is correct
9 Correct 3090 ms 488928 KB Output is correct
10 Correct 3066 ms 488928 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 7420 KB Output is correct
3 Correct 597 ms 496276 KB Output is correct
4 Correct 869 ms 496552 KB Output is correct
5 Correct 1427 ms 498024 KB Output is correct
6 Incorrect 2603 ms 498380 KB Output isn't correct
7 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 7420 KB Output is correct
3 Correct 3184 ms 488808 KB Output is correct
4 Correct 3108 ms 488788 KB Output is correct
5 Correct 3140 ms 488820 KB Output is correct
6 Correct 3249 ms 488800 KB Output is correct
7 Correct 3102 ms 488972 KB Output is correct
8 Correct 3270 ms 488864 KB Output is correct
9 Correct 3349 ms 488860 KB Output is correct
10 Correct 3166 ms 488800 KB Output is correct
11 Correct 3090 ms 488928 KB Output is correct
12 Correct 3066 ms 488928 KB Output is correct
13 Correct 597 ms 496276 KB Output is correct
14 Correct 869 ms 496552 KB Output is correct
15 Correct 1427 ms 498024 KB Output is correct
16 Incorrect 2603 ms 498380 KB Output isn't correct
17 Halted 0 ms 0 KB -