oj.uz

Submission #151040

# Submission time Handle Problem Language Result Execution time Memory
151040 2019-09-01T15:23:37 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 498976 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> uf;
	vector<set<pair<int,int>>> who;
	UnionFindFinches(int n=0):n(n),uf(n),who(n){
		for(int i=0;i<n;++i) uf[i]=i;
		for(int i=0;i<n;++i) who[i].insert({i,-1});
	}
	int find(int x){return x==uf[x]?x:find(uf[x]);}
	void join(int x, int y, int time){
		if((x=find(x))==(y=find(y))) return;
		uf[y]=x;
		for(auto i:who[y])
			who[x].insert({i.first, time});
		who[y].clear();
	}
	~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);

		for(int i=0;i<M;++i){
			int x, y; tie(x,y) = edges[i];
			if(F[y] == finch) swap(x,y);
			else if(F[y] == finch ||  (F[x] != finch && F[y] != finch && dsu.who[F[x]].size()<dsu.who[F[y]].size()))
				swap(x,y);
			dsu.join(x,y,i);
		}
		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 3184 ms 488832 KB Output is correct
2 Correct 3081 ms 488804 KB Output is correct
3 Correct 3122 ms 489028 KB Output is correct
4 Correct 3202 ms 488840 KB Output is correct
5 Correct 3220 ms 488924 KB Output is correct
6 Correct 3196 ms 488932 KB Output is correct
7 Correct 3056 ms 488828 KB Output is correct
8 Correct 3237 ms 489072 KB Output is correct
9 Correct 3136 ms 488976 KB Output is correct
10 Correct 3165 ms 488960 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 Execution timed out 5105 ms 498976 KB Time limit exceeded
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 8 ms 7416 KB Output is correct
3 Correct 3184 ms 488832 KB Output is correct
4 Correct 3081 ms 488804 KB Output is correct
5 Correct 3122 ms 489028 KB Output is correct
6 Correct 3202 ms 488840 KB Output is correct
7 Correct 3220 ms 488924 KB Output is correct
8 Correct 3196 ms 488932 KB Output is correct
9 Correct 3056 ms 488828 KB Output is correct
10 Correct 3237 ms 489072 KB Output is correct
11 Correct 3136 ms 488976 KB Output is correct
12 Correct 3165 ms 488960 KB Output is correct
13 Execution timed out 5105 ms 498976 KB Time limit exceeded
14 Halted 0 ms 0 KB -