oj.uz

Submission #826854

# Submission time Handle Problem Language Result Execution time Memory
826854 2023-08-16T05:29:48 Z 반딧불(#10373) Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 21344 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void solve();

int main(){
	input();
	solve();
}

int n, m, q;
int ex[100002], ey[100002];
vector<pair<int, int> > link[100002];
vector<int> timings[100002];
int arr[200002];
int query[200002];

int dfs(int x, int p, int t){
	//printf("%d %d %d\n", x, p, t);
	int ret = 1;
	for(auto y: link[x]){
		int nxt = y.first, idx = y.second;
		if(nxt == p || timings[idx].empty() || t < timings[idx][0]) continue;

		int nxtT = t;
		auto it = prev(upper_bound(timings[idx].begin(), timings[idx].end(), t));
		if((it - timings[idx].begin()) % 2 == 1) nxtT = *it;
		ret += dfs(nxt, x, nxtT);
	}
	return ret;
}

void input(){
	scanf("%d %d %d", &n, &m, &q);
	for(int i=1; i<n; i++){
		scanf("%d %d", &ex[i], &ey[i]);
		link[ex[i]].push_back(make_pair(ey[i], i));
		link[ey[i]].push_back(make_pair(ex[i], i));
	}
	for(int i=1; i<=m; i++){
		scanf("%d", &arr[i]);
		timings[arr[i]].push_back(i);
	}
	for(int i=1; i<=q; i++) scanf("%d", &query[i]);
}

void solve(){
	for(int i=1; i<n; i++){
		if((int)timings[i].size() % 2) timings[i].push_back(m);
	}

	for(int i=1; i<=q; i++){
		printf("%d\n", dfs(query[i], -1, m));
	}
}

Compilation message

synchronization.cpp: In function 'void input()':
synchronization.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d %d", &ex[i], &ey[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:48:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  for(int i=1; i<=q; i++) scanf("%d", &query[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 7 ms 5972 KB Output is correct
8 Correct 7 ms 6004 KB Output is correct
9 Correct 7 ms 5968 KB Output is correct
10 Correct 69 ms 15344 KB Output is correct
11 Correct 62 ms 15420 KB Output is correct
12 Correct 74 ms 14712 KB Output is correct
13 Correct 65 ms 15124 KB Output is correct
14 Correct 50 ms 14764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 18656 KB Output is correct
2 Correct 47 ms 17196 KB Output is correct
3 Correct 44 ms 19788 KB Output is correct
4 Correct 43 ms 18920 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 10 ms 6056 KB Output is correct
8 Correct 79 ms 15904 KB Output is correct
9 Correct 79 ms 15948 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 15952 KB Output is correct
2 Execution timed out 8080 ms 21344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 63 ms 6116 KB Output is correct
7 Correct 2041 ms 16652 KB Output is correct
8 Correct 80 ms 15948 KB Output is correct
9 Execution timed out 8053 ms 16316 KB Time limit exceeded
10 Halted 0 ms 0 KB -