oj.uz

Submission #149221

# Submission time Handle Problem Language Result Execution time Memory
149221 2019-09-01T06:00:12 Z From The Sky(#3630, WhipppedCream, top34051, zoomswk) Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 5000 ms 20560 KB 
//subtask K <= 1000

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

const int maxn = 1e5 + 5;
const int maxk = 1000 + 5;
const int inf = 1e8;

int n, m, k;
int a[maxn];
vector<int> have[maxk];
vector<pair<int,int>> way[maxn];
int dis[maxn];
int ans[maxk][maxk];

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
	n = F.size(); m = S.size(); k = K;
	for(int i=0;i<n;i++) {
		a[i] = F[i];
		have[a[i]].push_back(i);
	}
	for(int i=0;i<m;i++) {
		way[S[i]].push_back({E[i], i});
		way[E[i]].push_back({S[i], i});
	}
	for(int x=0;x<k;x++) for(int y=0;y<k;y++) ans[x][y] = -1;
	for(int x=0;x<k;x++) {
		//printf("solving %d\n",x);
		for(int u=0;u<n;u++) dis[u] = -1;
		priority_queue<pair<int,int>> heap;
		for(auto u : have[x]) {
			//printf("\thave %d\n",u);
			dis[u] = m;
			heap.push({dis[u], u});
		}
		while(!heap.empty()) {
			auto tmp = heap.top(); heap.pop();
			int u = tmp.second;
			if(tmp.first != dis[u]) continue;
			//printf("\tdis %d = %d\n",u,dis[u]);
			for(auto nxt : way[u]) {
				int v = nxt.first, val = nxt.second;
				if(dis[v] < min(dis[u], val)) {
					//printf("\t\t(%d -> %d) : %d\n",u,v,val);
					dis[v] = min(dis[u], val);
					heap.push({dis[v], v});
				}
			}
		}
		for(int u=0;u<n;u++) ans[x][a[u]] = max(ans[x][a[u]], dis[u]);
	}
}

int Separate(int A, int B){
	return ans[A][B] + 1;
}

/*
#include <stdio.h>
#include <stdlib.h>

static void my_assert(int TF, const char* message){
	if(!TF){ puts(message); exit(0); }
}

int main(){
	int N, M, K, Q;
	std::vector<int> F, S, E;

	my_assert(scanf("%d%d%d%d", &N, &M, &K, &Q) == 4, "Error: Invalid Input");
	my_assert(1 <= K && K <= N && N <= 300000, "Error: Invalid Input");
	my_assert(N - 1 <= M && M <= 1000000, "Error: Invalid Input");
	my_assert(1 <= Q && Q <= 300000, "Error: Invalid Input");

	for(int i = 0; i < N; i++){
		int a;
		my_assert(scanf("%d", &a) == 1, "Error: Invalid Input");
		my_assert(0 <= a && a < K, "Error: Invalid Input");
		F.push_back(a);
	}
	for(int i = 0; i < M; i++){
		int a, b;
		my_assert(scanf("%d%d", &a, &b) == 2, "Error: Invalid Input");
		my_assert(0 <= a && a < N && 0 <= b && b < N && a != b, "Error: Invalid Input");
		S.push_back(a), E.push_back(b);
	}
	Init(K, F, S, E);

	for(int i = 0; i < Q; i++){
		int a, b;
		my_assert(scanf("%d%d", &a, &b) == 2, "Error: Invalid Input");
		my_assert(0 <= a && a < K && 0 <= b && b < K && a != b, "Error: Invalid Input");
		printf("%d\n", Separate(a, b));
	}
	return 0;
}
*/

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 8804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 8 ms 2944 KB Output is correct
3 Correct 382 ms 19864 KB Output is correct
4 Correct 1059 ms 20240 KB Output is correct
5 Correct 2332 ms 20152 KB Output is correct
6 Correct 4313 ms 20328 KB Output is correct
7 Execution timed out 5092 ms 20560 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 8 ms 2944 KB Output is correct
3 Runtime error 117 ms 8804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -