Submission #1032243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032243		0npata	Swapping Cities (APIO20_swap)	C++17	100 / 100	298 ms	51096 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector

const int N = 100005;

vec<pair<int, int>> hist[N];
vec<int> okt(N, -1);

const int INF = 1e9+5;

struct Comp {
	pair<int, int> eps;
	vec<int> vs;
};

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	vec<Comp> comps(N);
	for(int i = 0; i<N; i++) {
		comps[i] = {{i, i}, {i}};
		hist[i] = {{i, 0}};
	}
	set<pair<int, pair<int, int>>> edges;
	for(int i = 0; i<M; i++) {
		edges.insert({W[i], {U[i], V[i]}});
	}

	vec<int> ci(N);
	iota(ci.begin(), ci.end(), 0);

	auto upd = [&](int i, int w) {
		if(okt[i] != -1) return;
		okt[i] = w;
	};

	for(auto [weight, eps] : edges) {
		auto [u, v] = eps;

		if(ci[u] == ci[v]) {
			upd(ci[u], weight);
			continue;
		}

		if(comps[ci[u]].vs.size() < comps[ci[v]].vs.size()) swap(u, v);


		if(u == comps[ci[u]].eps.second) swap(comps[ci[u]].eps.first, comps[ci[u]].eps.second);
		if(v == comps[ci[v]].eps.second) swap(comps[ci[v]].eps.first, comps[ci[v]].eps.second);

		if(okt[ci[v]] == -1 && u == comps[ci[u]].eps.first && v == comps[ci[v]].eps.first) {
			comps[ci[u]].eps = {comps[ci[u]].eps.second, comps[ci[v]].eps.second};
		}
		else {
			upd(ci[u], weight);
		}

		for(int w : comps[ci[v]].vs) {
			ci[w] = ci[u];
			comps[ci[u]].vs.push_back(w);
			hist[w].push_back({ci[u], weight});
		}
	}

	for(int i = 0; i<N; i++) {
		hist[i].push_back({-1, INF});
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int i = 0;
	int j = 0;

	//cerr << okt[1] << '\n';

	while(i<hist[X].size() && j < hist[Y].size()) {
		if(hist[X][i].first == hist[Y][j].first && okt[hist[X][i].first] != -1) {
			return max(max(hist[X][i].second, hist[Y][j].second), okt[hist[X][i].first]);
		}
		if(hist[X][i+1].second < hist[Y][j+1].second) {
			i++;
		}
		else {
			j++;
		}
	}


	return -1;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:78:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  while(i<hist[X].size() && j < hist[Y].size()) {
      |        ~^~~~~~~~~~~~~~~
swap.cpp:78:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  while(i<hist[X].size() && j < hist[Y].size()) {
      |                            ~~^~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27