Submission #146750

#	Time	Username	Problem	Language	Result	Execution time	Memory
146750		TadijaSebez	철도 요금 (JOI16_ho_t3)	C++11	100 / 100	209 ms	21068 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
int u[N],v[N],w[N],r[N],ans[N];
bool use[N];
vector<pair<int,int>> E[N];
int dist[N],dp[N],n,m,q;
void BFS()
{
	for(int i=1;i<=n;i++) dist[i]=N,dp[i]=0;
	queue<int> q;
	q.push(1);
	dist[1]=0;dp[1]=::q+1;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		ans[dp[x]]++;
		for(auto e:E[x])
		{
			int y,l;
			tie(y,l)=e;
			if(dist[y]>dist[x]+1)
			{
				dist[y]=dist[x]+1;
				dp[y]=0;
				q.push(y);
			}
			if(dist[y]==dist[x]+1) dp[y]=max(dp[y],min(dp[x],l));
		}
	}
	for(int i=1;i<=::q;i++) ans[i]+=ans[i-1];
}
int main()
{
	scanf("%i %i %i",&n,&m,&q);
	for(int i=1;i<=m;i++) scanf("%i %i",&u[i],&v[i]),w[i]=q+1;
	for(int i=1;i<=q;i++) scanf("%i",&r[i]),use[r[i]]=1,w[r[i]]=i;
	for(int i=1;i<=m;i++) E[u[i]].pb({v[i],w[i]}),E[v[i]].pb({u[i],w[i]});
	BFS();
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:38:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i",&u[i],&v[i]),w[i]=q+1;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
2016_ho_t3.cpp:39:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i",&r[i]),use[r[i]]=1,w[r[i]]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39