//subtask K <= 1000
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#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;
}
*/
Compilation message
island.cpp:3:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
8756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
392 ms |
19936 KB |
Output is correct |
| 4 |
Correct |
1116 ms |
20252 KB |
Output is correct |
| 5 |
Correct |
1992 ms |
20180 KB |
Output is correct |
| 6 |
Correct |
4531 ms |
20344 KB |
Output is correct |
| 7 |
Execution timed out |
5099 ms |
20576 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2816 KB |
Output is correct |
| 3 |
Runtime error |
111 ms |
8756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
