Submission #335803

#	Time	Username	Problem	Language	Result	Execution time	Memory
335803		ChrisT	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	240 ms	21868 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
vector<array<int,2>> adj[MN];
vector<array<int,2>> dagadj[MN];
int indeg[MN], ed[MN*2], dist[MN];
bool exists[MN*2];
int main() { 
	int n,m,qq;
	scanf ("%d %d %d",&n,&m,&qq);
	vector<array<int,2>> edges(m+1);
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d",&edges[i][0],&edges[i][1]);
		adj[edges[i][0]].push_back({edges[i][1],i});
		adj[edges[i][1]].push_back({edges[i][0],i});
	}
	memset(dist,0x3f,sizeof dist);
	queue<int> q; dist[1] = 0; q.push(1);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (auto &[u,i] : adj[cur]) {
			if (dist[cur] + 1 < dist[u]) {
				dist[u] = dist[cur] + 1;
				q.push(u); ed[i] = u; indeg[u] = 1;
				dagadj[cur].push_back({u,i});
			} else if (dist[cur] + 1 == dist[u]) {
				ed[i] = u; ++indeg[u]; dagadj[cur].push_back({u,i});
			}
		}
	}
	fill(exists+1,exists+m+1,true);
	int ans = n;
	for (int t = 1; t <= qq; t++) {
		int r; scanf ("%d",&r); 
		if (exists[r] && ed[r] && !(--indeg[ed[r]])) q.push(ed[r]), --ans;
		exists[r] = 0;
		while (!q.empty()) {
			int cur = q.front(); q.pop();
			for (auto &[u,i] : dagadj[cur]) {
				if (exists[i] && !(--indeg[u])) {
					--ans; q.push(u);
				}
				exists[i] = 0;
			}
		}
		printf ("%d\n",n-ans);
	}
	return 0;
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf ("%d %d %d",&n,&m,&qq);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:13:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf ("%d %d",&edges[i][0],&edges[i][1]);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:34:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   int r; scanf ("%d",&r);
      |          ~~~~~~^~~~~~~~~

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