Submission #150160

#TimeUsernameProblemLanguageResultExecution timeMemory
150160From The Sky (#200)Trip to the Galapagos Islands (FXCUP4_island)C++17
0 / 100
122 ms8800 KiB
//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 mlog = 17; const int inf = 1e8; int n, m, k; int a[maxn]; vector<int> have[maxk]; int head[maxn]; vector<pair<int,int>> way[maxn]; int h[maxn]; int par[maxn][20], up[maxn][20]; //int ans[maxk][maxk]; int findhead(int x) { if(head[x]==x) return x; return head[x] = findhead(head[x]); } void dfs(int u, int last) { //printf("dfs %d %d\n",u,last); h[u] = h[last] + 1; for(int i=1;i<=mlog;i++) { par[u][i] = par[par[u][i-1]][i-1]; up[u][i] = min(up[par[u][i-1]][i-1], up[u][i-1]); //printf("\tup %d %d = %d\n",u,i,up[u][i]); } for(auto tmp : way[u]) { int v = tmp.first, val = tmp.second; if(v == last) continue; par[v][0] = u; up[v][0] = val; dfs(v, u); } } int lca(int x, int y) { int res = m; if(h[x]<h[y]) swap(x,y); for(int i=mlog;i>=0;i--) { if(h[par[x][i]] >= h[y]) { //printf("par = %d\n",par[x][i]); //printf("\t*lca <= %d\n",up[x][i]); res = min(res, up[x][i]); x = par[x][i]; } } if(x==y) return res; for(int i=mlog;i>=0;i--) { if(i == 0 || par[x][i] != par[y][i]) { res = min(res, up[x][i]); res = min(res, up[y][i]); //printf("\tlca <= %d\n",up[x][i]); //printf("\tlca <= %d\n",up[y][i]); x = par[x][i]; y = par[y][i]; } } return res; } void Init(int K, vector<int> F, vector<int> S, vector<int> E){ n = F.size(); m = S.size(); k = K; for(int i=1;i<=n;i++) { a[i] = F[i-1]; have[a[i]].push_back(i); } for(int i=1;i<=n;i++) head[i] = i; for(int i=m-1;i>=0;i--) { S[i]++; E[i]++; if(findhead(S[i])!=findhead(E[i])) { head[findhead(S[i])] = findhead(E[i]); way[S[i]].push_back({E[i], i+1}); way[E[i]].push_back({S[i], i+1}); //printf("edge %d %d\n",S[i],E[i]); } } dfs(1,0); } int Separate(int A, int B){ if(have[A].empty() || have[B].empty()) return 0; int x = have[A][0], y = have[B][0]; return lca(x,y); //if((int)have[A].size() >= wow) return ans[A][B] + 1; //if((int)have[B].size() >= wow) return ans[B][A] + 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 (stderr)

island.cpp:2:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...