oj.uz

Submission #100878

# Submission time Handle Problem Language Result Execution time Memory
100878 2019-03-15T01:49:52 Z E869120 Synchronization (JOI13_synchronization) C++14
60 / 100
 140 ms 18340 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 15 ms 5760 KB Output is correct
8 Correct 15 ms 5888 KB Output is correct
9 Correct 15 ms 5888 KB Output is correct
10 Correct 119 ms 12976 KB Output is correct
11 Correct 133 ms 12816 KB Output is correct
12 Correct 95 ms 12288 KB Output is correct
13 Correct 107 ms 13044 KB Output is correct
14 Correct 140 ms 13272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 16440 KB Output is correct
2 Correct 68 ms 15020 KB Output is correct
3 Correct 66 ms 18340 KB Output is correct
4 Correct 60 ms 17400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 9 ms 5248 KB Output is correct
7 Correct 16 ms 5888 KB Output is correct
8 Correct 126 ms 13156 KB Output is correct
9 Correct 139 ms 16052 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13048 KB Output is correct
2 Correct 85 ms 16092 KB Output is correct
3 Correct 79 ms 16124 KB Output is correct
4 Correct 91 ms 16248 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -