oj.uz

Submission #149492

# Submission time Handle Problem Language Result Execution time Memory
149492 2019-09-01T06:36:00 Z お前はもう死んでいる(#3784, kuroni, nvmdava, tfg) Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 3085 ms 20600 KB 
#include "island.h"

#include <vector>
#include <algorithm>
#include <map>
#include <iostream>

const int ms = 100100;
int par[ms], when[ms];
std::vector<int> freq[ms];
std::vector< std::pair<int, int> > times[ms];
int getPar(int x) { return par[x] == x ? x : getPar(par[x]); }

int wtf;
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int N = F.size(), M = S.size();
	for(int i = 0; i < N; i++) {
		par[i] = i;
		when[i] = 1e9;
		freq[F[i]].push_back(i);
		times[i].emplace_back(F[i], 0);
	}
	wtf = M;
	for(int i = 0; i < M; i++) {
		int u = getPar(S[M-i-1]), v = getPar(E[M-i-1]);
		if(u == v) continue;
		if(times[u].size() > times[v].size()) {
			std::swap(u, v);
		}
		for(int j = 0; j < times[u].size(); j++) {
			times[v].emplace_back(times[u][j].first, i);
		}
		when[u] = i;
		par[u] = v;
	}
	for(int i = 0; i < N; i++) {
		std::sort(times[i].begin(), times[i].end());
	}
}

std::map<std::pair<int, int>, int> memo;


int Separate(int A, int B){
	if(freq[A].size() > freq[B].size()) {
		std::swap(A, B);
	}
	if(memo.count(std::pair<int, int>(A, B))) return memo[std::pair<int, int>(A, B)];
	int ans = 1e9;
	for(int i = 0; i < freq[A].size(); i++) {
		int u = freq[A][i];
		int cost = 0;
		while(1) {
			int id = std::lower_bound(times[u].begin(), times[u].end(), std::pair<int, int>(B, -1)) - times[u].begin();
			if(id < times[u].size() && times[u][id].first == B) {
				ans = std::min(ans, std::max(times[u][id].second, cost));
			}
			if(par[u] == u) break;
			cost = when[u];
			u = par[u];
		}
	}
	ans = wtf - ans;
	return memo[std::pair<int, int>(A, B)] = ans;
}

Compilation message

island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < times[u].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < freq[A].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
island.cpp:55:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(id < times[u].size() && times[u][id].first == B) {
       ~~~^~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 20540 KB Output is correct
2 Correct 332 ms 20532 KB Output is correct
3 Correct 330 ms 20532 KB Output is correct
4 Correct 388 ms 20600 KB Output is correct
5 Correct 300 ms 20532 KB Output is correct
6 Correct 303 ms 20540 KB Output is correct
7 Correct 373 ms 20436 KB Output is correct
8 Correct 333 ms 20532 KB Output is correct
9 Correct 333 ms 20412 KB Output is correct
10 Correct 390 ms 20532 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 10 ms 5120 KB Output is correct
3 Correct 240 ms 17632 KB Output is correct
4 Correct 373 ms 17788 KB Output is correct
5 Correct 645 ms 17636 KB Output is correct
6 Correct 1101 ms 17636 KB Output is correct
7 Correct 2013 ms 17660 KB Output is correct
8 Correct 3085 ms 17820 KB Output is correct
9 Correct 2402 ms 17932 KB Output is correct
10 Correct 1556 ms 17760 KB Output is correct
11 Correct 1756 ms 17764 KB Output is correct
12 Correct 1677 ms 17764 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 10 ms 5120 KB Output is correct
3 Correct 412 ms 20540 KB Output is correct
4 Correct 332 ms 20532 KB Output is correct
5 Correct 330 ms 20532 KB Output is correct
6 Correct 388 ms 20600 KB Output is correct
7 Correct 300 ms 20532 KB Output is correct
8 Correct 303 ms 20540 KB Output is correct
9 Correct 373 ms 20436 KB Output is correct
10 Correct 333 ms 20532 KB Output is correct
11 Correct 333 ms 20412 KB Output is correct
12 Correct 390 ms 20532 KB Output is correct
13 Correct 240 ms 17632 KB Output is correct
14 Correct 373 ms 17788 KB Output is correct
15 Correct 645 ms 17636 KB Output is correct
16 Correct 1101 ms 17636 KB Output is correct
17 Correct 2013 ms 17660 KB Output is correct
18 Correct 3085 ms 17820 KB Output is correct
19 Correct 2402 ms 17932 KB Output is correct
20 Correct 1556 ms 17760 KB Output is correct
21 Correct 1756 ms 17764 KB Output is correct
22 Correct 1677 ms 17764 KB Output is correct
23 Correct 1343 ms 17892 KB Output is correct
24 Correct 736 ms 17980 KB Output is correct
25 Correct 620 ms 17980 KB Output is correct
26 Correct 472 ms 17980 KB Output is correct
27 Correct 466 ms 18020 KB Output is correct
28 Correct 337 ms 18364 KB Output is correct
29 Correct 313 ms 18876 KB Output is correct
30 Correct 312 ms 19772 KB Output is correct
31 Correct 318 ms 20192 KB Output is correct
32 Correct 296 ms 20540 KB Output is correct