제출 #100877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100877		E869120	동기화 (JOI13_synchronization)	C++14	30 / 100	8086 ms	18488 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

int N, M, Q, A[100009], B[100009], uses[100009]; bool used[100009];
vector<pair<int, int>> L[100009]; vector<pair<int, int>>G[100009];

void dfs(int pos, int dep) {
	used[pos] = true;
	for (int i = 0; i < (int)G[pos].size(); i++) {
		int to = G[pos][i].first, id = G[pos][i].second;
		if (used[to] == true) continue;
		
		int pos1 = lower_bound(L[id].begin(), L[id].end(), make_pair(dep + 1, 0)) - L[id].begin(); pos1--;
		int r = -1;
		if (pos1 >= 0 && dep <= L[id][pos1].second) r = dep;
		else if (pos1 >= 0) r = L[id][pos1].second;
		if (r >= 0) dfs(to, r);
	}
}

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 1; i <= N - 1; i++) scanf("%d%d", &A[i],&B[i]);
	for (int i = 1; i <= N - 1; i++) uses[i] = -1;
	for (int i = 1; i <= N - 1; i++) { G[A[i]].push_back(make_pair(B[i], i)); G[B[i]].push_back(make_pair(A[i], i)); }
	
	for (int i = 1; i <= M; i++) {
		int p; scanf("%d", &p);
		if (uses[p] == -1) uses[p] = i;
		else { L[p].push_back(make_pair(uses[p], i - 1)); uses[p] = -1; }
	}
	for (int i = 1; i <= N - 1; i++) { if (uses[i] >= 1) L[i].push_back(make_pair(uses[i], M)); }
	
	for (int i = 1; i <= Q; i++) {
		int c; scanf("%d", &c);
		for (int j = 1; j <= N; j++) used[j] = false;
		dfs(c, M);
		int cnts = 0; for (int j = 1; j <= N; j++) { if(used[j] == true) cnts++; }
		printf("%d\n", cnts);
	}
	return 0;
}

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

synchronization.cpp: In function 'int main()':
synchronization.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:23:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N - 1; i++) scanf("%d%d", &A[i],&B[i]);
                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:28:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p);
          ~~~~~^~~~~~~~~~
synchronization.cpp:35:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int c; scanf("%d", &c);
          ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40