Submission #467797

#	Time	Username	Problem	Language	Result	Execution time	Memory
467797		keta_tsimakuridze	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1132 ms	64228 KiB

plan

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int par[N],p[N][20],w[N],n,m,k,Lg = 18,tmin[N],timer,tmout[N],d[N];
vector<pair<int,pii> > edges;
vector<pii> V[N],e;
vector<int> child[N],comp[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
void merge(int u,int v,int W) {
	u = par[u];
	v = par[v];
	if(v == u) return;
	if(comp[u].size() < comp[v].size()) swap(u,v);
	for(int i=0; i < comp[v].size();i++) {
		comp[u].push_back(comp[v][i]);
		par[comp[v][i]] = u;
	}
	p[v][0] = u;
	w[v] = W;
	child[u].push_back(v);
	
}
void dfs(int u) {
	tmin[u] = ++timer;
	for(int j = 1; j <= Lg; j++) p[u][j] = p[p[u][j-1]][j-1];
	for(int i=0;i<child[u].size();i++) {
		p[child[u][i]][0] = u;
		dfs(child[u][i]);
	}
	tmout[u] = ++timer;
}
bool check(int u,int v) {
	if(tmin[u] <= tmin[v] && tmout[u] >= tmout[v]) return 1;
	return 0;
}
int find_lca(int u,int v) {
	if(check(u,v)) return u;
	if(check(v,u)) return v;
	
	for(int j=Lg;j>=0;j--) {
		if(p[u][j] && !check(p[u][j],v)) u = p[u][j];
	}	
	return p[u][0];
} 
int get(int u,int v) {
	int ans = mod;
	if(v == u) return ans;
	for(int j=Lg;j>=0;j--) {
		if(p[u][j] && !check(p[u][j],v)) u = p[u][j];
	}		
	return w[u];
}
main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++) {
		int u,v,w;
		cin >> u >> v >> w;
		V[u].push_back({v,w});
		V[v].push_back({u,w});
		e.push_back({u,v});
	}
	for(int i=1;i<=n;i++) d[i] = mod,par[i] = i, comp[i].push_back(i);
	cin >> k;
	for(int i=1;i<=k;i++) {
		int a;
		cin >> a;
		d[a] = 0;
		q.push({0,a});
	}
	
	while(q.size()) {
		int u = q.top().s;
		int dist = q.top().f;
		q.pop(); 
		if(d[u] < dist) continue;
		for(int i=0;i<V[u].size();i++) {
			int v = V[u][i].f;
			if(d[v] > d[u] + V[u][i].s) {
				d[v] = d[u] + V[u][i].s;
				q.push({d[v],v});
			}
		}
	}
	for(int i = 0; i < e.size(); i++) {
		edges.push_back({min(d[e[i].f],d[e[i].s]),{e[i].f,e[i].s}});
	}
	sort(edges.rbegin(),edges.rend());
	for(int i = 0; i < edges.size(); i++) {
		merge(edges[i].s.f,edges[i].s.s,edges[i].f);
	}
	dfs(par[1]);
	int q;
	cin >> q;
	while(q--) {
		int u,v;
		cin >> u >> v;
		int lca = find_lca(u,v);
		cout<<min(get(u,lca),get(v,lca))<<endl;
	}
 }

Compilation message (stderr)

plan.cpp: In function 'void merge(int, int, int)':
plan.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0; i < comp[v].size();i++) {
      |               ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'void dfs(int)':
plan.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0;i<child[u].size();i++) {
      |              ~^~~~~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0;i<V[u].size();i++) {
      |               ~^~~~~~~~~~~~
plan.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0; i < e.size(); i++) {
      |                 ~~^~~~~~~~~~
plan.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~

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