oj.uz

Submission #151054

# Submission time Handle Problem Language Result Execution time Memory
151054 2019-09-01T16:08:03 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 3364 ms 496668 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 3306 ms 488884 KB Output is correct
2 Correct 3182 ms 488768 KB Output is correct
3 Correct 3210 ms 488776 KB Output is correct
4 Correct 3197 ms 489020 KB Output is correct
5 Correct 3364 ms 488804 KB Output is correct
6 Correct 3270 ms 488856 KB Output is correct
7 Correct 3312 ms 488912 KB Output is correct
8 Correct 3176 ms 488824 KB Output is correct
9 Correct 3318 ms 488880 KB Output is correct
10 Correct 3330 ms 488856 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 9 ms 7416 KB Output is correct
3 Incorrect 622 ms 496668 KB Output isn't correct
4 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 9 ms 7416 KB Output is correct
3 Correct 3306 ms 488884 KB Output is correct
4 Correct 3182 ms 488768 KB Output is correct
5 Correct 3210 ms 488776 KB Output is correct
6 Correct 3197 ms 489020 KB Output is correct
7 Correct 3364 ms 488804 KB Output is correct
8 Correct 3270 ms 488856 KB Output is correct
9 Correct 3312 ms 488912 KB Output is correct
10 Correct 3176 ms 488824 KB Output is correct
11 Correct 3318 ms 488880 KB Output is correct
12 Correct 3330 ms 488856 KB Output is correct
13 Incorrect 622 ms 496668 KB Output isn't correct
14 Halted 0 ms 0 KB -