oj.uz

Submission #151088

# Submission time Handle Problem Language Result Execution time Memory
151088 2019-09-01T17:20:40 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 491156 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() > 12*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 3202 ms 488892 KB Output is correct
2 Correct 3430 ms 488964 KB Output is correct
3 Correct 3186 ms 488804 KB Output is correct
4 Correct 3249 ms 488864 KB Output is correct
5 Correct 3159 ms 488880 KB Output is correct
6 Correct 3152 ms 488932 KB Output is correct
7 Correct 2958 ms 488800 KB Output is correct
8 Correct 3190 ms 488832 KB Output is correct
9 Correct 3144 ms 488844 KB Output is correct
10 Correct 3133 ms 488968 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 556 ms 490648 KB Output is correct
4 Correct 712 ms 491156 KB Output is correct
5 Correct 1358 ms 486276 KB Output is correct
6 Correct 2572 ms 486236 KB Output is correct
7 Correct 4848 ms 486196 KB Output is correct
8 Execution timed out 5104 ms 486224 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 3202 ms 488892 KB Output is correct
4 Correct 3430 ms 488964 KB Output is correct
5 Correct 3186 ms 488804 KB Output is correct
6 Correct 3249 ms 488864 KB Output is correct
7 Correct 3159 ms 488880 KB Output is correct
8 Correct 3152 ms 488932 KB Output is correct
9 Correct 2958 ms 488800 KB Output is correct
10 Correct 3190 ms 488832 KB Output is correct
11 Correct 3144 ms 488844 KB Output is correct
12 Correct 3133 ms 488968 KB Output is correct
13 Correct 556 ms 490648 KB Output is correct
14 Correct 712 ms 491156 KB Output is correct
15 Correct 1358 ms 486276 KB Output is correct
16 Correct 2572 ms 486236 KB Output is correct
17 Correct 4848 ms 486196 KB Output is correct
18 Execution timed out 5104 ms 486224 KB Time limit exceeded
19 Halted 0 ms 0 KB -