oj.uz

답안 #150093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150093 2019-09-01T07:42:18 Z ummm(#3574, cerberus, aayush9, knandy) 갈라파고스 여행 (FXCUP4_island) C++17
31 / 100
 5000 ms 508520 KB 
#include "island.h"

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

const int MAX_M = 300000;
const int GAP = 480;

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);
		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[MAX_M/GAP+2];

vector<pair<int,int>> edges;
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[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);
	}
}

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])
		UF[bucket].join(pos[A][0], i, 1);
	for(auto i:pos[B])
		UF[bucket].join(pos[B][0], i, 1);

	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;
		}
	}
	assert(ans != -1);
	UF[bucket].rollback();
	return memo[A][B] = ans;
}

Subtask #1
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3577 ms 508516 KB Output is correct
2 Correct 3690 ms 508384 KB Output is correct
3 Correct 3626 ms 508516 KB Output is correct
4 Correct 3924 ms 508512 KB Output is correct
5 Correct 4438 ms 508384 KB Output is correct
6 Correct 3774 ms 508388 KB Output is correct
7 Correct 3477 ms 508388 KB Output is correct
8 Correct 4426 ms 508516 KB Output is correct
9 Correct 3742 ms 508520 KB Output is correct
10 Correct 3536 ms 508516 KB Output is correct

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Execution timed out 5124 ms 505956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 3577 ms 508516 KB Output is correct
4 Correct 3690 ms 508384 KB Output is correct
5 Correct 3626 ms 508516 KB Output is correct
6 Correct 3924 ms 508512 KB Output is correct
7 Correct 4438 ms 508384 KB Output is correct
8 Correct 3774 ms 508388 KB Output is correct
9 Correct 3477 ms 508388 KB Output is correct
10 Correct 4426 ms 508516 KB Output is correct
11 Correct 3742 ms 508520 KB Output is correct
12 Correct 3536 ms 508516 KB Output is correct
13 Execution timed out 5124 ms 505956 KB Time limit exceeded
14 Halted 0 ms 0 KB -