oj.uz

Submission #151043

# Submission time Handle Problem Language Result Execution time Memory
151043 2019-09-01T15:28:24 Z aayush9 Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 498092 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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 UnionFindPathCompression {
	int n;
	vector<int> uf;
	UnionFindPathCompression(int n=0):n(n),uf(n){
		for(int i=0;i<n;++i) uf[i]=i;
	}
	int find(int x){return uf[x] = x==uf[x]?x:find(uf[x]);}
	void join(int x, int y){
		if((x=find(x))==(y=find(y))) return;
		uf[y]=x;
	}
};

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);
	}


	vector<pair<int,int>> queries;
	for(int finch=0;finch<K;++finch) if(pos[finch].size() >= GAP)
		for(int i=finch+1;i<K;++i) queries.push_back({finch,i});
	
	int Q = queries.size();
	
	vector<int> lo(Q,0), hi(Q,M-1);

	for(int iter=19;iter--;){

		vector<vector<int>> mid(M);
		for(auto i=0;i<Q;++i)
			mid[(lo[i]+hi[i])/2].push_back(i);

		UnionFind dsu(N);
		for(int i=0;i<M;++i){
			dsu.join(edges[i].first, edges[i].second, 0);
			for(auto j:mid[i]){
				int A = queries[j].first, B = queries[j].second;
				
				if(pos[A].size() > pos[B].size()) swap(A,B);

				int ok = 0;

				for(auto i:pos[A]) dsu.join(pos[A][0], i, 1);

				for(auto i:pos[B])
					ok |= dsu.find(pos[A][0]) == dsu.find(i);

				if(ok)
					hi[j] = i;
				else
					lo[j] = i + 1;

				dsu.rollback();
			}
		}
	}

	for(int i=0;i<Q;++i){
		// cout << queries[i].first << ' ' << queries[i].second << ' ' << M - hi[i] << '\n';
		memo[queries[i].first][queries[i].second] = max(memo[queries[i].first][queries[i].second], M - hi[i]);
	}
}

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 3362 ms 496744 KB Output is correct
2 Correct 3407 ms 496740 KB Output is correct
3 Correct 3472 ms 496716 KB Output is correct
4 Correct 3427 ms 496720 KB Output is correct
5 Correct 3437 ms 496908 KB Output is correct
6 Correct 3397 ms 496692 KB Output is correct
7 Correct 3585 ms 496676 KB Output is correct
8 Correct 3534 ms 496760 KB Output is correct
9 Correct 3431 ms 496668 KB Output is correct
10 Correct 3473 ms 496780 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 913 ms 494608 KB Output is correct
4 Correct 1160 ms 494320 KB Output is correct
5 Correct 1675 ms 494148 KB Output is correct
6 Correct 2719 ms 494148 KB Output is correct
7 Correct 4212 ms 494408 KB Output is correct
8 Execution timed out 5070 ms 498092 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 3362 ms 496744 KB Output is correct
4 Correct 3407 ms 496740 KB Output is correct
5 Correct 3472 ms 496716 KB Output is correct
6 Correct 3427 ms 496720 KB Output is correct
7 Correct 3437 ms 496908 KB Output is correct
8 Correct 3397 ms 496692 KB Output is correct
9 Correct 3585 ms 496676 KB Output is correct
10 Correct 3534 ms 496760 KB Output is correct
11 Correct 3431 ms 496668 KB Output is correct
12 Correct 3473 ms 496780 KB Output is correct
13 Correct 913 ms 494608 KB Output is correct
14 Correct 1160 ms 494320 KB Output is correct
15 Correct 1675 ms 494148 KB Output is correct
16 Correct 2719 ms 494148 KB Output is correct
17 Correct 4212 ms 494408 KB Output is correct
18 Execution timed out 5070 ms 498092 KB Time limit exceeded
19 Halted 0 ms 0 KB -