Submission #100878

#	Time	Username	Problem	Language	Result	Execution time	Memory
100878		E869120	Synchronization (JOI13_synchronization)	C++14	60 / 100	140 ms	18340 KiB

synchronization

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

int N, M, Q, A[100009], B[100009], col[100009], ans[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)); }
	
	if (Q == 1) {
		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);
		}
	}
	else {
		for (int i = 1; i <= N; i++) col[i] = -1;
		int cntv = 0;
		for (int i = 1; i <= N; i++) {
			col[i] = M; cntv++; int cx = i - 1;
			while (cx >= 1) {
				int id = cx;
				int pos1 = lower_bound(L[id].begin(), L[id].end(), make_pair(col[cx + 1] + 1, 0)) - L[id].begin(); pos1--;
				int r = -1;
				if (pos1 >= 0 && col[cx + 1] <= L[id][pos1].second) r = col[cx + 1];
				else if (pos1 >= 0) r = L[id][pos1].second;
				
				if (r == col[cx]) break;
				col[cx] = r; if (r == -1) cntv--;
				cx--;
			}
			ans[i] += cntv;
		}
		for (int i = 1; i <= N; i++) col[i] = -1;
		cntv = 0;
		for (int i = N; i >= 1; i--) {
			col[i] = M; cntv++; int cx = i;
			while (cx < N) {
				int id = cx;
				int pos1 = lower_bound(L[id].begin(), L[id].end(), make_pair(col[cx] + 1, 0)) - L[id].begin(); pos1--;
				int r = -1;
				if (pos1 >= 0 && col[cx] <= L[id][pos1].second) r = col[cx];
				else if (pos1 >= 0) r = L[id][pos1].second;
				
				if (r == col[cx + 1]) break;
				col[cx + 1] = r; if (r == -1) cntv--;
				cx++;
			}
			ans[i] += cntv;
		}
		
		for (int i = 1; i <= Q; i++) {
			int c; scanf("%d", &c);
			printf("%d\n", ans[c] - 1);
		}
	}
	return 0;
}

Compilation message (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:36:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int c; scanf("%d", &c);
           ~~~~~^~~~~~~~~~
synchronization.cpp:80:16: 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: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40