oj.uz

Submission #149153

# Submission time Handle Problem Language Result Execution time Memory
149153 2019-09-01T05:50:28 Z ummm(#3574, cerberus, aayush9, knandy) Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 4209 ms 479076 KB 
#include "island.h"

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

int GAP = 500;

struct UnionFind {
	int n,comp;
	vector<int> uf,si,c;
	UnionFind(int n=0):n(n),comp(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;comp--;
		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;comp++;
		}
	}
} UF[605];

vector<pair<int,int>> edges;
vector<int> F;

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
	int 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());

	UnionFind cur(K);

	::F = F;

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

int Separate(int A, int B){
	int bucket = 0, start = 0, ans = 0;
	for(int i=0;i<edges.size();i+=GAP){
		if(UF[i/GAP].find(A) == UF[i/GAP].find(B)){
			bucket = (i-GAP)/GAP, start = i - GAP;
			break;
		}
	}
	// cout << start << " ";
	for(int i=start;i<start+GAP && i<edges.size(); ++i){
		// cout << "Joining " << F[edges[i].first] << ' ' << F[edges[i].second] << '\n';
		UF[bucket].join(F[edges[i].first], F[edges[i].second]);
		if(UF[bucket].find(A) == UF[bucket].find(B)){
			ans = i;
			break;
		}
	}
	UF[bucket].rollback();
	return edges.size() - ans;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edges.size();i+=GAP){
              ~^~~~~~~~~~~~~
island.cpp:60:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=start;i<start+GAP && i<edges.size(); ++i){
                                 ~^~~~~~~~~~~~~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 4209 ms 479076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -