Submission #41548

#TimeUsernameProblemLanguageResultExecution timeMemory
41548IvanCEvacuation plan (IZhO18_plan)C++14
54 / 100
4091 ms41392 KiB
#include <bits/stdc++.h> using namespace std; knuth_b gen((rand() ^ rand() ^ rand()) ^ (rand() << (rand() % 17) )); typedef pair<int,int> ii; typedef tuple<int,int,int> trinca; const int INF = 1e9; const int MAXN = 1e5 + 10; const int MAXL = 2; vector<ii> grafo[MAXN],adj[MAXN],arestas; vector<trinca> Kruskal; priority_queue<ii, vector<ii>, greater<ii> > pq; int ancestral[MAXN][MAXL],liga[MAXN][MAXL],nivel[MAXN],processado[MAXN],dist[MAXN],n,m,dsu_parent[MAXN],dsu_weight[MAXN]; int find(int x){ if(x == dsu_parent[x]) return x; return dsu_parent[x] = find(dsu_parent[x]); } void join(int x,int y){ x = find(x); y = find(y); if(dsu_weight[x] < dsu_weight[y]) swap(x,y); dsu_parent[y] = x; dsu_weight[x] += dsu_weight[y]; } void dfs(int v,int p){ for(int i = 1;i<MAXL;i++){ int z = ancestral[v][i-1]; if(z != -1){ ancestral[v][i] = ancestral[z][i-1]; liga[v][i] = min(liga[v][i-1],liga[z][i-1]); } } for(int i = 0;i<adj[v].size();i++){ int u = adj[v][i].first, w = adj[v][i].second; if(u == p) continue; nivel[u] = nivel[v] + 1; ancestral[u][0] = v; liga[u][0] = w; dfs(u,v); } } int LCA(int u,int v){ int ans = INF; while(u != v){ if(nivel[u] < nivel[v]) swap(u,v); ans = min(ans,liga[u][0]); u = ancestral[u][0]; } return ans; } int main(){ memset(ancestral,-1,sizeof(ancestral)); scanf("%d %d",&n,&m); for(int i = 1;i<=n;i++){ dsu_parent[i] = i; dsu_weight[i] = 1; } for(int i = 1;i<=m;i++){ int u,v,w; scanf("%d %d %d",&u,&v,&w); grafo[u].push_back(ii(v,w)); grafo[v].push_back(ii(u,w)); arestas.push_back(ii(u,v)); } int q; scanf("%d",&q); for(int i = 1;i<=q;i++){ int x; scanf("%d",&x); pq.push(ii(0,x)); } while(!pq.empty()){ int d = pq.top().first, v = pq.top().second; pq.pop(); if(processado[v]) continue; processado[v] = 1; dist[v] = d; for(int i = 0;i<grafo[v].size();i++){ int u = grafo[v][i].first, w = grafo[v][i].second; if(!processado[u]) pq.push(ii(d+w,u)); } } for(int i = 0;i<arestas.size();i++){ int u = arestas[i].first, v = arestas[i].second; Kruskal.push_back(make_tuple(min(dist[u],dist[v]),u,v)); } sort(Kruskal.begin(),Kruskal.end()); for(int i = (int)Kruskal.size()-1;i>=0;i--){ int u = get<1>(Kruskal[i]) , v = get<2>(Kruskal[i]), w = get<0>(Kruskal[i]); if(find(u) != find(v)){ join(u,v); adj[u].push_back(ii(v,w)); adj[v].push_back(ii(u,w)); } } dfs((gen() % n)+1,-1); scanf("%d",&q); while(q--){ int u,v; scanf("%d %d",&u,&v); printf("%d\n",LCA(u,v)); } return 0; }

Compilation message (stderr)

plan.cpp: In function 'void dfs(int, int)':
plan.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<adj[v].size();i++){
                ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<grafo[v].size();i++){
                 ~^~~~~~~~~~~~~~~~
plan.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<arestas.size();i++){
                ~^~~~~~~~~~~~~~~
plan.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
plan.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
plan.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
plan.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
plan.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...