oj.uz

Submission #151090

# Submission time Handle Problem Language Result Execution time Memory
151090 2019-09-01T17:22:12 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 491096 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() > 20*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 3143 ms 488936 KB Output is correct
2 Correct 3118 ms 488900 KB Output is correct
3 Correct 3151 ms 488900 KB Output is correct
4 Correct 3150 ms 488928 KB Output is correct
5 Correct 3194 ms 488924 KB Output is correct
6 Correct 3095 ms 488844 KB Output is correct
7 Correct 3108 ms 488888 KB Output is correct
8 Correct 3100 ms 488856 KB Output is correct
9 Correct 2972 ms 488868 KB Output is correct
10 Correct 3039 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 7416 KB Output is correct
3 Correct 552 ms 490804 KB Output is correct
4 Correct 768 ms 491096 KB Output is correct
5 Correct 1323 ms 486248 KB Output is correct
6 Correct 2409 ms 486192 KB Output is correct
7 Correct 4686 ms 486300 KB Output is correct
8 Execution timed out 5109 ms 486364 KB Time limit exceeded
9 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 3143 ms 488936 KB Output is correct
4 Correct 3118 ms 488900 KB Output is correct
5 Correct 3151 ms 488900 KB Output is correct
6 Correct 3150 ms 488928 KB Output is correct
7 Correct 3194 ms 488924 KB Output is correct
8 Correct 3095 ms 488844 KB Output is correct
9 Correct 3108 ms 488888 KB Output is correct
10 Correct 3100 ms 488856 KB Output is correct
11 Correct 2972 ms 488868 KB Output is correct
12 Correct 3039 ms 488928 KB Output is correct
13 Correct 552 ms 490804 KB Output is correct
14 Correct 768 ms 491096 KB Output is correct
15 Correct 1323 ms 486248 KB Output is correct
16 Correct 2409 ms 486192 KB Output is correct
17 Correct 4686 ms 486300 KB Output is correct
18 Execution timed out 5109 ms 486364 KB Time limit exceeded
19 Halted 0 ms 0 KB -