Submission #168801

#	Time	Username	Problem	Language	Result	Execution time	Memory
168801		abil	Evacuation plan (IZhO18_plan)	C++14	100 / 100	893 ms	55348 KiB

plan

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long
 
using namespace std;
 
const int N = (1e5 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);
 
vector<pair<int,int > > g[N];
vector<pair<int,pair<int,int > > > vec;
vector<pair<int,int > > road;
 
int dist[N], par[N], sz[N], up[20][N], mn[20][N], tin[N], tout[N], timer;
 
int find(int v){
	if(v == par[v]){
		return v;
	}
	return par[v] = find(par[v]);
}
 
void dsu(int a,int b){
	a = find(a);
	b = find(b);
	if(sz[a] < sz[b]){
		swap(a, b);
	}
	sz[a] += sz[b];
	par[b] = a;
}
 
void dfs(int v,int pr,int w){
	up[0][v] = pr;
	mn[0][v] = w;
	tin[v] = ++timer;
	for(int i = 1;i <= 19; i++){
		up[i][v] = up[i - 1][up[i - 1][v]];
		mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
	}
	for(auto to : g[v]){
		if(to.fr != pr){
			dfs(to.fr, v, to.sc);
		}
	}
	tout[v] = ++timer;
}
 
bool upper(int a,int b){
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
 
int get(int a,int b){
	int res = INF;
	if(upper(a, b)){
		for(int i = 19;i >= 0; i--){
			if(!upper(up[i][b], a)){
				res = min(res, mn[i][b]);
				b = up[i][b];
			}
		}
		res = min(res, mn[0][b]);
	}
	else
	if(upper(b, a)){
		for(int i = 19;i >= 0; i--){
			if(!upper(up[i][a], b)){
				res = min(res, mn[i][a]);
				a = up[i][a];
			}
		}
		res = min(res, mn[0][a]);
	}
	else{
		for(int i = 19;i >= 0; i--){
			if(!upper(up[i][b], a)){
				res = min(res, mn[i][b]);
				b = up[i][b];
			}
		}
		res = min(res, mn[0][b]);
		for(int i = 19;i >= 0; i--){
			if(!upper(up[i][a], b)){
				res = min(res, mn[i][a]);
				a = up[i][a];
			}
		}
		res = min(res, mn[0][a]);
	}
	return res;
}
main()
{
	int n, m, u, v, w;
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n; i++){
		par[i] = i;
		sz[i] = 1;
	}
	for(int i = 1;i <= m; i++){
		scanf("%d%d%d", &u, &v, &w);
		g[u].pb({v,w});
		g[v].pb({u,w});
		road.pb({u, v});
	}
	int k;
	priority_queue<pair<int,int > > q;
	scanf("%d", &k);
	memset(dist, 0x3f3f3f3f,sizeof(dist));
	for(int i = 0;i < k; i++){
		scanf("%d", &v);
		dist[v] = 0;
		q.push({0,v});
	}
	while(!q.empty()){
		v = q.top().sc;
		q.pop();
		for(auto to : g[v]){
			if(dist[to.fr] > dist[v] + to.sc){
				dist[to.fr] = dist[v] + to.sc;
				q.push({-dist[to.fr], to.fr});
			}
		}
	}
	for(int i = 1;i <= n; i++){
		g[i].clear();
	}
	for(int i = 0;i < m; i++){
		vec.pb({min(dist[road[i].fr],dist[road[i].sc]),{road[i].fr,road[i].sc}});
	}
	sort(all(vec));
	reverse(all(vec));
	for(int i = 0;i < m; i++){
		v = vec[i].sc.fr, u = vec[i].sc.sc, w = min(dist[u], dist[v]);
		if(find(v) != find(u)){
			g[v].pb({u, w});
			g[u].pb({v, w});
			dsu(u,v);
		}
	}
	dfs(1, 1, INF);
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &u, &v);
		printf("%d\n", get(u, v));
	}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp:98:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:101: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:107: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:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v);
   ~~~~~^~~~~~~~~~
plan.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
plan.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

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