oj.uz

Submission #150039

# Submission time Handle Problem Language Result Execution time Memory
150039 2019-09-01T07:35:58 Z ummm(#3574, cerberus, aayush9, knandy) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 4627 ms 489316 KB 
#include "island.h"

#include <bits/stdc++.h>
using namespace std;

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){
		if((x=find(x))==(y=find(y))) return false;
		if(si[x]<si[y]) swap(x,y);
		// cout << "Joining " << x << ' ' << y << '\n';
		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[605];

vector<pair<int,int>> edges;
vector<int> F;
vector<int> pos[100005];

int M, N;

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<M;++i)
		edges[i] = make_pair(S[i], E[i]);
	reverse(edges.begin(), edges.end());

	for(int i=0;i<(int)F.size();++i)
		pos[F[i]].push_back(i);

	UnionFind cur(N);

	::F = F;

	for(int i=0;i<M;++i){
		if(i%GAP==0) UF[i/GAP] = cur;
		cur.join(edges[i].first, edges[i].second, 0);
	}
}

map<int,int> memo[100005];
int Separate(int A, int B){
	if(A>B) swap(A,B);
	if(memo[A].count(B)) return memo[A][B];

	int bucket = 0, start = 0, ans = -1;
	for(int i=0;i<M;i+=GAP){
		if(UF[i/GAP].find(pos[A][0]) == UF[i/GAP].find(pos[B][0]))
			break;
		start = i, bucket = i/GAP;
	}
	for(auto i:pos[A]) {
		// cout << i << ' ' << pos[A][0] << '\n';
		UF[bucket].join(pos[A][0],i, 1);
	}
	for(auto i:pos[B]) {
		// cout << i << ' ' << pos[B][0] << '\n';
		UF[bucket].join(pos[B][0],i, 1);
	}

	for(int i=start;i<start+GAP && i<M; ++i){
		// cout << edges[i].first << ' ' <<edges[i].second << '\n';
		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;
		}
	}
	assert(ans != -1);
	UF[bucket].rollback();
	return memo[A][B] = ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4499 ms 489312 KB Output is correct
2 Correct 4627 ms 489316 KB Output is correct
3 Correct 4378 ms 489184 KB Output is correct
4 Correct 4529 ms 489316 KB Output is correct
5 Correct 4318 ms 489316 KB Output is correct
6 Correct 4608 ms 489312 KB Output is correct
7 Correct 4273 ms 489316 KB Output is correct
8 Correct 3378 ms 489236 KB Output is correct
9 Correct 4141 ms 489316 KB Output is correct
10 Correct 4214 ms 489312 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7296 KB Output is correct
3 Incorrect 435 ms 486756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7296 KB Output is correct
3 Correct 4499 ms 489312 KB Output is correct
4 Correct 4627 ms 489316 KB Output is correct
5 Correct 4378 ms 489184 KB Output is correct
6 Correct 4529 ms 489316 KB Output is correct
7 Correct 4318 ms 489316 KB Output is correct
8 Correct 4608 ms 489312 KB Output is correct
9 Correct 4273 ms 489316 KB Output is correct
10 Correct 3378 ms 489236 KB Output is correct
11 Correct 4141 ms 489316 KB Output is correct
12 Correct 4214 ms 489312 KB Output is correct
13 Incorrect 435 ms 486756 KB Output isn't correct
14 Halted 0 ms 0 KB -