oj.uz

Submission #151017

# Submission time Handle Problem Language Result Execution time Memory
151017 2019-09-01T15:00:27 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 498852 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 3333 ms 488908 KB Output is correct
2 Correct 3255 ms 493176 KB Output is correct
3 Correct 3235 ms 493076 KB Output is correct
4 Correct 3220 ms 493060 KB Output is correct
5 Correct 3256 ms 493032 KB Output is correct
6 Correct 3252 ms 493080 KB Output is correct
7 Correct 3147 ms 493076 KB Output is correct
8 Correct 3182 ms 493188 KB Output is correct
9 Correct 3466 ms 493044 KB Output is correct
10 Correct 3463 ms 493172 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 5130 ms 498852 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 3333 ms 488908 KB Output is correct
4 Correct 3255 ms 493176 KB Output is correct
5 Correct 3235 ms 493076 KB Output is correct
6 Correct 3220 ms 493060 KB Output is correct
7 Correct 3256 ms 493032 KB Output is correct
8 Correct 3252 ms 493080 KB Output is correct
9 Correct 3147 ms 493076 KB Output is correct
10 Correct 3182 ms 493188 KB Output is correct
11 Correct 3466 ms 493044 KB Output is correct
12 Correct 3463 ms 493172 KB Output is correct
13 Execution timed out 5130 ms 498852 KB Time limit exceeded
14 Halted 0 ms 0 KB -