oj.uz

Submission #151073

# Submission time Handle Problem Language Result Execution time Memory
151073 2019-09-01T16:53:35 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 503452 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){
		if(x==uf[x]) return x;
		uf[x] = find(uf[x]);
		adj[uf[x]].push_back(x);
		return uf[x];
	}
	void join(int x, int y, int time, int special){
		if((x=find(x))==(y=find(y))) return;
		
		if(x != special){
			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[y].clear();
		};

		adj[x].push_back(y);
		if(x == special) 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, 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,i,pos[finch][0]);
		}

		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 2975 ms 488928 KB Output is correct
2 Correct 3067 ms 488848 KB Output is correct
3 Correct 3206 ms 488968 KB Output is correct
4 Correct 2989 ms 488848 KB Output is correct
5 Correct 3122 ms 488812 KB Output is correct
6 Correct 3131 ms 488932 KB Output is correct
7 Correct 3106 ms 488844 KB Output is correct
8 Correct 3152 ms 489000 KB Output is correct
9 Correct 3158 ms 488968 KB Output is correct
10 Correct 3119 ms 488904 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 611 ms 499568 KB Output is correct
4 Correct 952 ms 502648 KB Output is correct
5 Correct 1780 ms 502804 KB Output is correct
6 Correct 3295 ms 503176 KB Output is correct
7 Execution timed out 5090 ms 503452 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 7416 KB Output is correct
3 Correct 2975 ms 488928 KB Output is correct
4 Correct 3067 ms 488848 KB Output is correct
5 Correct 3206 ms 488968 KB Output is correct
6 Correct 2989 ms 488848 KB Output is correct
7 Correct 3122 ms 488812 KB Output is correct
8 Correct 3131 ms 488932 KB Output is correct
9 Correct 3106 ms 488844 KB Output is correct
10 Correct 3152 ms 489000 KB Output is correct
11 Correct 3158 ms 488968 KB Output is correct
12 Correct 3119 ms 488904 KB Output is correct
13 Correct 611 ms 499568 KB Output is correct
14 Correct 952 ms 502648 KB Output is correct
15 Correct 1780 ms 502804 KB Output is correct
16 Correct 3295 ms 503176 KB Output is correct
17 Execution timed out 5090 ms 503452 KB Time limit exceeded
18 Halted 0 ms 0 KB -