제출 #48518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48518		Pajaraja	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1243 ms	50112 KiB

plan

#include <bits/stdc++.h>
using namespace std;
vector<int> g[100007],gt[100007],c[100007],z;
int d[100007],arr[100007],dsu[100007],p[20][100007],in[100007],out[100007],n,ti,l[20][100007];
bool vi[100007];
int root(int u)
{
	while(dsu[u]!=u)
	{
		dsu[u]=dsu[dsu[u]];
		u=dsu[u];
	}
	return u;
}
bool cmp(int a,int b) {return d[a]>d[b];}
void simuldij()
{
	priority_queue<pair<int,int> > pq;
	for(int i=0;i<z.size();i++) pq.push(make_pair(0,z[i]));
	while(!pq.empty())
	{
		int s=pq.top().second,a=-pq.top().first;
		pq.pop();
		if(vi[s]) continue;
		vi[s]=true;
		d[s]=a;
		for(int i=0;i<g[s].size();i++) pq.push(make_pair(-a-c[s][i],g[s][i]));
	}
}
void dfs(int s,int f)
{
	p[0][s]=f;
	l[0][s]=d[s];
	in[s]=ti++;
	for(int i=0;i<gt[s].size();i++) dfs(gt[s][i],s);
	out[s]=ti++;
}
void lcainit()
{
	dfs(arr[n],0);
	in[0]=-1;
	out[0]=1000000000;
	l[0][0]=2000000000;
	d[0]=2000000000;
	for(int i=1;i<20;i++) for(int j=1;j<=n;j++) {l[i][j]=min(l[i-1][j],l[i-1][p[i-1][j]]); p[i][j]=p[i-1][p[i-1][j]];}
}
bool insub(int a,int b) {return in[a]>=in[b] && out[a]<=out[b];}
int query(int a,int b)
{
	int x=a,y=b,sol=2000000000;
	for(int i=19;i>=0;i--) if(!insub(b,p[i][x])) {sol=min(sol,l[i][x]); x=p[i][x];}
	sol=min(sol,d[x]);
	if(!insub(b,a)) sol=min(sol,d[p[0][x]]);
	for(int i=19;i>=0;i--) if(!insub(a,p[i][y])) {sol=min(sol,l[i][y]); y=p[i][y];}
	sol=min(sol,d[y]);
	if(!insub(a,b)) sol=min(sol,d[p[0][y]]);
	return sol;
}
int main()
{
	int m,za,q,t;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int t1,t2,t3;
		scanf("%d%d%d",&t1,&t2,&t3);
		g[t1].push_back(t2);
		g[t2].push_back(t1);
		c[t1].push_back(t3);
		c[t2].push_back(t3);
	}
	scanf("%d",&za);
	for(int i=0;i<za;i++) {scanf("%d",&t); z.push_back(t);}
	simuldij();
	for(int i=1;i<=n;i++) arr[i]=dsu[i]=i;
	fill(vi,vi+n+1,false);
	sort(arr+1,arr+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		vi[arr[i]]=true;
		for(int j=0;j<g[arr[i]].size();j++) if(vi[g[arr[i]][j]] && root(g[arr[i]][j])!=arr[i]) {gt[arr[i]].push_back(root(g[arr[i]][j])); dsu[root(g[arr[i]][j])]=arr[i];} 
	}
	lcainit();
	scanf("%d",&q);
	for(int i=0;i<q;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		printf("%d\n",query(t1,t2));
	}
}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'void simuldij()':
plan.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<z.size();i++) pq.push(make_pair(0,z[i]));
              ~^~~~~~~~~
plan.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[s].size();i++) pq.push(make_pair(-a-c[s][i],g[s][i]));
               ~^~~~~~~~~~~~
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<gt[s].size();i++) dfs(gt[s][i],s);
              ~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[arr[i]].size();j++) if(vi[g[arr[i]][j]] && root(g[arr[i]][j])!=arr[i]) {gt[arr[i]].push_back(root(g[arr[i]][j])); dsu[root(g[arr[i]][j])]=arr[i];} 
               ~^~~~~~~~~~~~~~~~~
plan.cpp:62: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:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t1,&t2,&t3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&za);
  ~~~~~^~~~~~~~~~
plan.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<za;i++) {scanf("%d",&t); z.push_back(t);}
                         ~~~~~^~~~~~~~~
plan.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
plan.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
   ~~~~~^~~~~~~~~~~~~~~~

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