oj.uz

Submission #151056

# Submission time Handle Problem Language Result Execution time Memory
151056 2019-09-01T16:10:29 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 3332 ms 496508 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();
			};
			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, 0);
 
		for(int i=0;i<M;++i){
			int x, y; tie(x,y) = edges[i];
			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);
			// cout << finch << ' '<<F[i.first] << ' ' << memo[finch][F[i.first]] << '\n';
		}
	}
}
 
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 3133 ms 488972 KB Output is correct
2 Correct 3055 ms 488900 KB Output is correct
3 Correct 3164 ms 489008 KB Output is correct
4 Correct 3103 ms 488876 KB Output is correct
5 Correct 3265 ms 488776 KB Output is correct
6 Correct 3087 ms 488876 KB Output is correct
7 Correct 3114 ms 488904 KB Output is correct
8 Correct 3246 ms 488944 KB Output is correct
9 Correct 3154 ms 488836 KB Output is correct
10 Correct 3332 ms 488880 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 598 ms 496056 KB Output is correct
4 Correct 880 ms 496508 KB Output is correct
5 Incorrect 1361 ms 496356 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 3133 ms 488972 KB Output is correct
4 Correct 3055 ms 488900 KB Output is correct
5 Correct 3164 ms 489008 KB Output is correct
6 Correct 3103 ms 488876 KB Output is correct
7 Correct 3265 ms 488776 KB Output is correct
8 Correct 3087 ms 488876 KB Output is correct
9 Correct 3114 ms 488904 KB Output is correct
10 Correct 3246 ms 488944 KB Output is correct
11 Correct 3154 ms 488836 KB Output is correct
12 Correct 3332 ms 488880 KB Output is correct
13 Correct 598 ms 496056 KB Output is correct
14 Correct 880 ms 496508 KB Output is correct
15 Incorrect 1361 ms 496356 KB Output isn't correct
16 Halted 0 ms 0 KB -