Submission #168795

#	Time	Username	Problem	Language	Result	Execution time	Memory
168795		abil	Evacuation plan (IZhO18_plan)	C++14	0 / 100	4038 ms	24056 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 = (2e5 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);

vector<pair<int,int > > g[N], gg[N];
vector<pair<int,int > > vec;

int dist[N], par[N], sz[N], up[22][N], mn[22][N], tin[N], tout[N], timer, was[N];

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][b], a)){
				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][b], a)){
				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});
		gg[u].pb({v,w});
		gg[v].pb({u,w});
	}
	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;
		w = -q.top().fr;
		if(w > dist[v]){
			continue;
		}
		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();
		vec.pb({dist[i], i});
	}
	sort(all(vec));
	reverse(all(vec));
	for(int i = 0;i < n; i++){
		v = vec[i].sc, w = vec[i].fr;
		was[v] = 1;
		for(auto to : gg[v]){
			if(!was[to.fr]){
				continue;
			}
			u = to.fr;
			if(find(v) != find(u)){
				g[v].pb({u, min(w,dist[u])});
				g[u].pb({v, min(w,dist[u])});
				dsu(u,v);
			}
		}
	}
	dfs(vec[n - 1].sc, vec[n - 1].sc, 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:97:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:100: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:106: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:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
plan.cpp:160: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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46