oj.uz

답안 #150489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150489 2019-09-01T08:30:51 Z ummm(#3574, cerberus, aayush9, knandy) 갈라파고스 여행 (FXCUP4_island) C++17
31 / 100
 4243 ms 488956 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[MAX_M/GAP+2];

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

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

	assert(UF[bucket].find(pos[A][0]) != UF[bucket].find(pos[B][0]));

	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 3807 ms 488932 KB Output is correct
2 Correct 4243 ms 488932 KB Output is correct
3 Correct 3637 ms 488932 KB Output is correct
4 Correct 3804 ms 488800 KB Output is correct
5 Correct 3747 ms 488928 KB Output is correct
6 Correct 3937 ms 488956 KB Output is correct
7 Correct 4032 ms 488928 KB Output is correct
8 Correct 3716 ms 488928 KB Output is correct
9 Correct 3616 ms 488928 KB Output is correct
10 Correct 3551 ms 488932 KB Output is correct

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Runtime error 389 ms 486372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 3807 ms 488932 KB Output is correct
4 Correct 4243 ms 488932 KB Output is correct
5 Correct 3637 ms 488932 KB Output is correct
6 Correct 3804 ms 488800 KB Output is correct
7 Correct 3747 ms 488928 KB Output is correct
8 Correct 3937 ms 488956 KB Output is correct
9 Correct 4032 ms 488928 KB Output is correct
10 Correct 3716 ms 488928 KB Output is correct
11 Correct 3616 ms 488928 KB Output is correct
12 Correct 3551 ms 488932 KB Output is correct
13 Runtime error 389 ms 486372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -