oj.uz

Submission #151086

# Submission time Handle Problem Language Result Execution time Memory
151086 2019-09-01T17:17:48 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 491480 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>>> adj;
	UnionFindFinches(int n=0):n(n),si(n,1),uf(n),adj(n){
		for(int i=0;i<n;++i) uf[i]=i;
	}
	int find(int x){
		if(x==uf[x]) return x;
		return find(uf[x]);
	}
	void join(int x, int y, int time, int special){
		if((x=find(x))==(y=find(y))) return;
		
		if(y == special || x != special){
			if(si[x]<si[y]) swap(x,y);
			si[x]+=si[y];
		}

		uf[y]=x;


		adj[x].push_back({y,time});
	}
};
 
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() >= 2*GAP){
		UnionFindFinches dsu(N);

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


		function<void(int,int)> dfs = [&](int y, int min_so_far){
			memo[finch][F[y]] = max(memo[finch][F[y]], min_so_far);
			for(auto i:dsu.adj[y]) dfs(i.first, min(min_so_far,i.second));
		};
		for(auto i:dsu.adj[pos[finch][0]])
			dfs(i.first, i.second);
		// for(auto i:dsu.who[pos[finch][0]])
		// 	memo[finch][F[i.first]] = max(memo[finch][F[i.first]], 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 2959 ms 488904 KB Output is correct
2 Correct 2982 ms 488948 KB Output is correct
3 Correct 3114 ms 488852 KB Output is correct
4 Correct 3033 ms 488952 KB Output is correct
5 Correct 3108 ms 488980 KB Output is correct
6 Correct 3143 ms 488824 KB Output is correct
7 Correct 3024 ms 488784 KB Output is correct
8 Correct 3155 ms 488844 KB Output is correct
9 Correct 2967 ms 488972 KB Output is correct
10 Correct 3030 ms 488860 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 7388 KB Output is correct
3 Correct 554 ms 490820 KB Output is correct
4 Correct 711 ms 491132 KB Output is correct
5 Correct 1109 ms 491304 KB Output is correct
6 Correct 2092 ms 491396 KB Output is correct
7 Execution timed out 5088 ms 491480 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 7416 KB Output is correct
2 Correct 8 ms 7388 KB Output is correct
3 Correct 2959 ms 488904 KB Output is correct
4 Correct 2982 ms 488948 KB Output is correct
5 Correct 3114 ms 488852 KB Output is correct
6 Correct 3033 ms 488952 KB Output is correct
7 Correct 3108 ms 488980 KB Output is correct
8 Correct 3143 ms 488824 KB Output is correct
9 Correct 3024 ms 488784 KB Output is correct
10 Correct 3155 ms 488844 KB Output is correct
11 Correct 2967 ms 488972 KB Output is correct
12 Correct 3030 ms 488860 KB Output is correct
13 Correct 554 ms 490820 KB Output is correct
14 Correct 711 ms 491132 KB Output is correct
15 Correct 1109 ms 491304 KB Output is correct
16 Correct 2092 ms 491396 KB Output is correct
17 Execution timed out 5088 ms 491480 KB Time limit exceeded
18 Halted 0 ms 0 KB -