Submission #571418

#	Time	Username	Problem	Language	Result	Execution time	Memory
571418		duytuandao21	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4045 ms	64632 KiB

plan

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
const int N = 2e6+7;
int n,m,k,q,dist[N],NNP[N];
vector<ii> adj[N];
void DIJKSTRA() {
	vector<int> d(n+1,1e9+7);
	priority_queue< ii, vector<ii>, greater<ii> > dt;
	for(int i=1;i<=n;i++) {
		if(NNP[i] == 1) {
			d[i] = 0;
			dt.push({0,i});
		}
	}
	while(!dt.empty()) {
		int u = dt.top().se;
		int val = dt.top().fi;
		dt.pop();
		if(d[u] != val) continue;
		for(ii w : adj[u]) {
			int v = w.se;
			int he = w.fi;

			if(d[v] > he + val) {
				d[v] = he + val;
				dt.push({d[v], v});
			}
		}
	}
	for(int i=1;i<=n;i++) dist[i] = min(dist[i], d[i]);
}
bool check(int val,int x,int y) {
	queue<int> s;
	//int ok[n+1];
	//for(int i=1;i<=n;i++) ok[i] = 0;
	vector<int> ok(n+1,0);
	ok[x] = 1;
	if(dist[x] >= val) s.push(x);
	while(!s.empty()) {
		int u = s.front();  s.pop();
		//cout<<u<<" ";
		for(ii w : adj[u]) {
			int v = w.se;
			if(ok[v] == 0 && dist[v] >= val) {
				ok[v] = 1;
				s.push(v);
			}
		}
	}
	if(ok[y] == 1) return true;
	return false;
}
void solve(int u,int v) {
	int l = 0;
	int r = 1e8;
	int ans;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(check(mid,u,v) == true) {
			ans = mid;
			l = mid + 1;
		} else r = mid - 1;
	}
	cout<<ans<<'\n';
}
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) dist[i] = 1e9+7;
	for(int i=1;i<=m;i++) {
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({w,v});
		adj[v].push_back({w,u});
	}
	cin>>k;
	while(k--) {
		int x;
		cin>>x;
		NNP[x] = 1;
	}
	DIJKSTRA();
	cin>>q;
	while(q--) {
		int u,v;
		cin>>u>>v;
		solve(u,v);
	}
	//for(int i=1;i<=n;i++) cout<<dist[i]<<" "; cout<<'\n';
	//if(check(6,1,6)==true) cout<<"hayquadit";
	//solve(1,6);
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void solve(int, int)':
plan.cpp:67:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  cout<<ans<<'\n';
      |             ^~~~

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