Submission #173248

#	Time	Username	Problem	Language	Result	Execution time	Memory
173248		LinusTorvaldsFan	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1404 ms	41924 KiB

plan

#include <iostream>
#include <vector>
#include <memory.h>
#include <unordered_set>
#include <algorithm>
#include <set>
 
using namespace std;
 
typedef long long ll;
 
const int maxn=100010;
vector<pair<int,int>> G[maxn];
 
int dist[maxn];
 
int dsu[maxn];
int sz[maxn];
 
struct DSU{
  DSU(int n){
    for(int i=1;i<=n;i++)dsu[i]=i,sz[i]=1;
  }
  
  int find(int v){
    if(dsu[v]==v)return v;
    return dsu[v]=find(dsu[v]);
  }
  
  void merge(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b)return;
    if(sz[a]>sz[b]){
      sz[a]+=sz[b];
      dsu[b]=a;
    }
    else{
      sz[b]+=sz[a];
      dsu[a]=b;
    }
  }
};
 
bool added[maxn];
 
signed main(){
  memset(dist,63,sizeof(dist));
  ios_base::sync_with_stdio(0);cin.tie(0);
  int n; cin>>n;
  int m; cin>>m;
  for(int i=0;i<m;i++){
    int u,v,w; cin>>u>>v>>w;
    G[u].emplace_back(v,w);
    G[v].emplace_back(u,w);
  }
  int k; cin>>k;
  dist[0]=0;
  for(int i=0;i<k;i++){
    int x;cin>>x;
    G[0].emplace_back(x,0);
  }
  set<pair<int,int>> dijkstra;
  dijkstra.emplace(0,0);
  while(dijkstra.size()){
    int d=dijkstra.begin()->first;
    int v=dijkstra.begin()->second;
    dijkstra.erase(dijkstra.begin());
    if(d!=dist[v])continue;
    for(auto &edge:G[v]){
      int u=edge.first;
      int w=edge.second;
      if(dist[u]>d+w){
	dijkstra.erase({dist[u],u});
	dist[u]=d+w;
	dijkstra.emplace(dist[u],u);
      }
    }
  }
  
  vector<pair<int,int>> vertexes;
  for(int v=1;v<=n;v++)vertexes.emplace_back(dist[v],v);
  
  sort(vertexes.rbegin(),vertexes.rend());
  
  int q;
  cin>>q;
  vector<pair<int,int>> que;
  for(int i=0;i<q;i++){
    int a,b; cin>>a>>b;
    que.emplace_back(a,b);
  }
 
  vector<pair<int,int>> bin_search(q);
  
  for(int i=0;i<q;i++)bin_search[i]={0,n-1};
  vector<vector<int>>queries(n);
  
  
  for(int t=0;t<17;t++){
    for(int i=0;i<n;i++)queries[i].clear();
    for(int i=0;i<q;i++){
      int m=(bin_search[i].first+bin_search[i].second)>>1;
      queries[m].emplace_back(i);
    }
    DSU dsu(n);
    memset(added,0,sizeof(added));
    for(int i=0;i<n;i++){
      int cur_v=vertexes[i].second;
      for(auto &edge:G[cur_v]){
	int u=edge.first;
	if(added[u]) dsu.merge(u,cur_v);
      }
      added[cur_v]=true;
      for(auto &query:queries[i]){
	int a=que[query].first;
	int b=que[query].second;
	
	if(!added[a]||!added[b]){
	  bin_search[query].first=i;
	} else {
	  if(dsu.find(a)!=dsu.find(b)){
	    bin_search[query].first=i;
	  }else{
	    bin_search[query].second=i;
	  }
	}
      }
    }
  }
  for(int i=0;i<q;i++){
   cout<<vertexes[bin_search[i].second].first<<"\n";
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46