Submission #1141690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141690		nuutsnoynton	철도 요금 (JOI16_ho_t3)	C++17	0 / 100	49 ms	9284 KiB

2016_ho_t3

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll M = 2e5 + 2;
const ll N = 1e5 + 2;
ll x[M], y[M], a[M];
int D[N], cnt[N];
vector < ll > adj[N];
ll used[M] = {0};


int main() {
// std::ios::sync_with_stdio(false);
 //cin.tie(0);
 //cout.tie(0);
	ll n, m, r, i, j,x1, y1, s, ans, t;

	scanf("%d %d %d",& n,& m,& t);
	for (i = 1; i <= n ; i ++) {
		D[i] = 1e9;
	}
	D[1] = 0;
	
	for (i = 1; i <= m; i ++) {
		scanf("%d %d",& x[i],& y[i]);
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	queue < ll > q;
	q.push(1);
	r = 0;	
	cnt[1] = 1;
	while(!q.empty()) {
		x1 = q.front();
		r ++;
		q.pop();
		for ( ll X : adj[x1]) {
			if ( D[X] != 1e9)  {
				if ( D[X] == D[x1] + 1) {
					cnt[X] += cnt[x1];
				}
				continue;
			}
			D[X] = D[x1] + 1;
			cnt[X] += cnt[x1];
			q.push(X);
		}
	}
	for (i = 1; i <= n; i ++) adj[i].clear();
	for (i = 1; i <= m; i ++) {
		if ( D[x[i]] == D[y[i]] + 1) {
			adj[y[i]].push_back(x[i]);
		}
		if ( D[y[i]] == D[x[i]] + 1) {
			adj[x[i]].push_back(y[i]);
		}
	}
	vector < ll > Ans;
	cnt[1] = 1;
	s = 0;
	D[1] = 0;
	
	for (i = 1; i <= t; i ++) {
		scanf("%d",& r);
		x1 = x[r];
		y1 = y[r];
		if ( D[x1] == D[y1] + 1 && cnt[y1] != 0 && cnt[x1] != 0) {
			r = cnt[y1];
			q.push(x1);
			while(!q.empty()) {
				x1 = q.front();
				cnt[x1] -= r;
				if ( cnt[x1] == 0) s ++;
				q.pop();
				for ( ll X : adj[x1]) {
					q.push(X);
				}
			}
		}
		if ( D[y1] == D[x1] + 1 && cnt[x1] != 0 && cnt[y1] != 0) {
			r = cnt[x1];
			q.push(y1);
			while(!q.empty()) {
				x1 = q.front();
				cnt[x1] -= r;
				if ( cnt[x1] == 0) s ++;
				q.pop();
				for ( ll X : adj[x1]) {
					q.push(X);
				}
			}
		}
		Ans.push_back(s);
	}
	
	
	
	for (i = 0; i < Ans.size(); i ++) {
		printf("%d\n", Ans[i]);
	}
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%d %d %d",& n,& m,& t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 scanf("%d %d",& x[i],& y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |                 scanf("%d",& r);
      |                 ~~~~~^~~~~~~~~~

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