oj.uz

Submission #28208

# Submission time Handle Problem Language Result Execution time Memory
28208 2017-07-15T18:20:58 Z abcdef6199 Synchronization (JOI13_synchronization) C++
0 / 100
 79 ms 8268 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;

const int MAXN = (int) 2e5 + 10;
int n, m, q, d[MAXN];
int a[MAXN], f[MAXN];
int L[MAXN], R[MAXN];
int cnt[MAXN];
II range[MAXN];

int FindLeft(int i) {
	if (L[i] == i) return i;
	return L[i] = FindLeft(L[i]);
}

int FindRight(int i) {
	if (R[i] == i) return i;
	return R[i] = FindRight(R[i]);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n - 1; ++i) {
		int u, v; scanf("%d%d", &u, &v);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &d[i]);
		f[i] = a[d[i]]; a[d[i]] ^= 1;
	}

	for (int i = 1; i <= n; ++i) L[i] = R[i] = i, range[i] = II(i, i);
	for (int i = m; i >= 1; --i) {
		if (f[i] == 1) continue;
		L[d[i] + 1] = d[i];
		R[d[i]] = d[i] + 1;
		int x = FindLeft(d[i]);
		int y = FindRight(d[i]);
		range[d[i]] = II(x, y);
		range[d[i] + 1] = II(x, y);
	}

	for (int i = 1; i <= n; ++i) cnt[range[i].first]++, cnt[range[i].second + 1]--;
	for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];

	while (q--) {
		int x; scanf("%d", &x);
		printf("%d\n", cnt[x]);
	}
	return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:25:29: 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:27:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d", &u, &v);
                                  ^
synchronization.cpp:30:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
                     ^
synchronization.cpp:49:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8268 KB Output is correct
2 Incorrect 0 ms 8268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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