oj.uz

답안 #151066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151066 2019-09-01T16:41:08 Z aayush9 갈라파고스 여행 (FXCUP4_island) C++17
31 / 100
 3261 ms 496800 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> si,uf;
	vector<vector<pair<int,int>>> who;
	vector<vector<int>> adj;
	UnionFindFinches(int n=0):n(n),si(n,1),uf(n),who(n),adj(n){
		for(int i=0;i<n;++i) uf[i]=i;
		for(int i=0;i<n;++i) who[i].push_back({i,-1});
	}
	int find(int x){return x==uf[x]?x:find(uf[x]);}
	void join(int x, int y, int time, int merge){
		if((x=find(x))==(y=find(y))) return;
		
		if(!merge){
			if(si[x]<si[y]) swap(x,y);
		}

		si[x]+=si[y];
		uf[y]=x;

		function<void(int,int)> dfs = [&](int x, int y){
			for(auto i:who[y]) who[x].push_back({i.first, time});
			who[y].clear();
			si[y] = 0;
			for(auto i:adj[y]) dfs(x, i);
			adj[y].clear();
		};

		adj[x].push_back(y);
		
		if(merge) dfs(x, y);
	}
};
 
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);
		dsu.who[pos[finch][0]].reserve(N+1);

		for(auto i:pos[finch]) dsu.join(pos[finch][0], i, -1, 1);
 
		for(int i=0;i<M;++i){
			int x, y; tie(x,y) = edges[i];
			if(F[x] == finch && F[y] == finch) continue;
			if(F[y] == finch) swap(x,y);
			dsu.join(x,y,i,F[x] == finch);
		}

		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

# 결과 실행 시간 메모리 Grader output
1 Correct 3085 ms 488800 KB Output is correct
2 Correct 3255 ms 488888 KB Output is correct
3 Correct 3210 ms 488852 KB Output is correct
4 Correct 3256 ms 488876 KB Output is correct
5 Correct 3247 ms 488864 KB Output is correct
6 Correct 3111 ms 488992 KB Output is correct
7 Correct 3131 ms 488888 KB Output is correct
8 Correct 3125 ms 488884 KB Output is correct
9 Correct 3261 ms 488976 KB Output is correct
10 Correct 3242 ms 488796 KB Output is correct

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 605 ms 496520 KB Output is correct
4 Correct 925 ms 496688 KB Output is correct
5 Incorrect 1499 ms 496800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 3085 ms 488800 KB Output is correct
4 Correct 3255 ms 488888 KB Output is correct
5 Correct 3210 ms 488852 KB Output is correct
6 Correct 3256 ms 488876 KB Output is correct
7 Correct 3247 ms 488864 KB Output is correct
8 Correct 3111 ms 488992 KB Output is correct
9 Correct 3131 ms 488888 KB Output is correct
10 Correct 3125 ms 488884 KB Output is correct
11 Correct 3261 ms 488976 KB Output is correct
12 Correct 3242 ms 488796 KB Output is correct
13 Correct 605 ms 496520 KB Output is correct
14 Correct 925 ms 496688 KB Output is correct
15 Incorrect 1499 ms 496800 KB Output isn't correct
16 Halted 0 ms 0 KB -