oj.uz

Submission #603444

# Submission time Handle Problem Language Result Execution time Memory
603444 2022-07-24T06:57:11 Z 장태환(#8428) Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 24016 KB 
#include <bits/stdc++.h>
using namespace std;
int N, M, K;
vector<pair<int, int>>link[100100];
vector<pair<int, int>>arr[100100];
map<int, int>x;
int dfs(int n, int ti, int p = 0)
{
	int ans = 1;
	int i;
	for (i = 0; i < link[n].size(); i++)
	{
		if (link[n][i].first == p)
			continue;
		int v = lower_bound(arr[link[n][i].second].begin(), arr[link[n][i].second].end(), make_pair(ti, 0)) - arr[link[n][i].second].begin();
		if (v == 0)
			continue;
		else
			ans+=dfs(link[n][i].first, min(arr[link[n][i].second][v - 1].second, ti), n);
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> K;
	int i;
	for (i = 1; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		link[a].push_back({ b,i });
		link[b].push_back({ a,i });
	}
	for (i = 0; i < M; i++)
	{
		int a;
		cin >> a;
		if (x[a])
		{
			arr[a].push_back({ x[a],i + 1 });
			x[a] = 0;
		}
		else
		{
			x[a] = i + 1;
		}
	}
	for (i = 1; i < N; i++)
	{
		if (x[i])
		{
			arr[i].push_back({ x[i],M + 1 });
		}
	}
	while (K--)
	{
		int a;
		cin >> a;
		cout << dfs(a, M+5) << '\n';
	}
}

Compilation message

synchronization.cpp: In function 'int dfs(int, int, int)':
synchronization.cpp:11:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (i = 0; i < link[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5016 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 5024 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 14 ms 6316 KB Output is correct
8 Correct 18 ms 6328 KB Output is correct
9 Correct 15 ms 6336 KB Output is correct
10 Correct 165 ms 18468 KB Output is correct
11 Correct 151 ms 18532 KB Output is correct
12 Correct 143 ms 17868 KB Output is correct
13 Correct 159 ms 18276 KB Output is correct
14 Correct 137 ms 18232 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21908 KB Output is correct
2 Correct 83 ms 20228 KB Output is correct
3 Correct 90 ms 23452 KB Output is correct
4 Correct 94 ms 22568 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5016 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 17 ms 6324 KB Output is correct
8 Correct 188 ms 18884 KB Output is correct
9 Correct 257 ms 18680 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 18636 KB Output is correct
2 Execution timed out 8020 ms 24016 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5084 KB Output is correct
6 Correct 103 ms 6384 KB Output is correct
7 Correct 3510 ms 19416 KB Output is correct
8 Correct 236 ms 18640 KB Output is correct
9 Execution timed out 8080 ms 18596 KB Time limit exceeded
10 Halted 0 ms 0 KB -