oj.uz

Submission #151067

# Submission time Handle Problem Language Result Execution time Memory
151067 2019-09-01T16:43:10 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 3238 ms 497192 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);
		
		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 3166 ms 488900 KB Output is correct
2 Correct 3178 ms 488996 KB Output is correct
3 Correct 3146 ms 488904 KB Output is correct
4 Correct 3114 ms 488844 KB Output is correct
5 Correct 3175 ms 488928 KB Output is correct
6 Correct 3144 ms 488800 KB Output is correct
7 Correct 3238 ms 488908 KB Output is correct
8 Correct 3078 ms 488940 KB Output is correct
9 Correct 3030 ms 488840 KB Output is correct
10 Correct 3073 ms 488912 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 600 ms 496656 KB Output is correct
4 Correct 927 ms 497192 KB Output is correct
5 Correct 1574 ms 497092 KB Output is correct
6 Incorrect 2888 ms 497008 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 7416 KB Output is correct
3 Correct 3166 ms 488900 KB Output is correct
4 Correct 3178 ms 488996 KB Output is correct
5 Correct 3146 ms 488904 KB Output is correct
6 Correct 3114 ms 488844 KB Output is correct
7 Correct 3175 ms 488928 KB Output is correct
8 Correct 3144 ms 488800 KB Output is correct
9 Correct 3238 ms 488908 KB Output is correct
10 Correct 3078 ms 488940 KB Output is correct
11 Correct 3030 ms 488840 KB Output is correct
12 Correct 3073 ms 488912 KB Output is correct
13 Correct 600 ms 496656 KB Output is correct
14 Correct 927 ms 497192 KB Output is correct
15 Correct 1574 ms 497092 KB Output is correct
16 Incorrect 2888 ms 497008 KB Output isn't correct
17 Halted 0 ms 0 KB -