oj.uz

Submission #965344

# Submission time Handle Problem Language Result Execution time Memory
965344 2024-04-18T11:04:26 Z Alkaser_ID Jail (JOI22_jail) C++17
0 / 100
 1256 ms 1048576 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;

vector<ll> adj[N], path[N];
ll a[N], b[N], dep[N], p[N][20];
ll ind[N], curr[N];
bool vis[N], com[N];
inline void dfs1(ll i, ll pr) {
	p[i][0] = pr;
	dep[i] = dep[pr] + 1;
	for (ll j = 1; j < 20; ++j) {
		p[i][j] = p[p[i][j - 1]][j - 1];
	}
	for (ll j = 0; j < adj[i].size(); ++j) {
		if (adj[i][j] == pr) continue;
		dfs1(adj[i][j], i);
	}
}
inline ll parent(ll x, ll d) {
	if (d == 0) return x;
	for (ll j = 0; j < 20; ++j) {
		if ((1ll << j) & d) return parent(p[x][j], d - (1ll << j));
	}
}
inline ll lca(ll x, ll y) {
	if (dep[x] > dep[y]) swap(x, y);
	y = parent(y, dep[y] - dep[x]);
	if (x == y) return x;
	for (ll j = 19; j >= 0; --j) {
		if (p[x][j] != p[y][j]) {
			x = p[x][j];
			y = p[y][j];
		}
	}
	return p[x][0];
}
inline void pth(ll i) {
	ll ca = lca(a[i], b[i]);
	if (ca == a[i]) {
		ll cr = b[i];
		for (;;) {
			path[i].push_back(cr);
			cr = p[cr][0];
			if (cr == ca) break;
		}
		reverse(path[i].begin(), path[i].end());
	}
	else if (ca == b[i]) {
		ll cr = a[i];
		for (;;) {
			cr = p[cr][0];
			path[i].push_back(cr);
			if (cr == ca) break;
		}
	}
	else {
		ll cr = a[i];
		for (;;) {
			cr = p[cr][0];
			path[i].push_back(cr);
			if (cr == ca) break;
		}
		vector<ll> as; 
		cr = b[i];
		for (;;) {
			as.push_back(cr);
			cr = p[cr][0];
			if (cr == ca) break;
		}
		reverse(as.begin(), as.end());
		for (ll j = 0; j < as.size(); ++j) path[i].push_back(as[j]);
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for (; t--;) {
		ll n; cin >> n;
		for (ll i = 1; i <= n; ++i) {
			adj[i].clear(); path[i].clear();
			vis[i] = false; com[i] = false;
		}
		for (ll i = 1; i < n; ++i) {
			ll u, v; cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		dfs1(1, 0);
		ll q; cin >> q;
		for (ll i = 1; i <= q; ++i) {
			cin >> a[i] >> b[i];
			pth(i);
			vis[a[i]] = true; curr[i] = a[i];
			ind[i] = 0;
		}
		bool ans = true;
		for (ll completed = 0; completed < q;) {
			bool fl = true;
			for (ll i = 1; i <= q; ++i) {
				if (com[i]) continue;
				for (;;) {
					ll dx = ind[i];
					if (vis[path[i][dx]]) break;
					vis[curr[i]] = false;
					curr[i] = path[i][dx];
					fl = false;
					vis[curr[i]] = true;
					++ind[i];
					if (ind[i] == path[i].size()) { com[i] = true; ++completed; break; }
				}
			}
			if (fl) { ans = false; break; }
		}
		if (ans) cout << "Yes\n";
		else cout << "No\n";
	}
}

Compilation message

jail.cpp: In function 'void dfs1(ll, ll)':
jail.cpp:20:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (ll j = 0; j < adj[i].size(); ++j) {
      |                 ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'void pth(ll)':
jail.cpp:77:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (ll j = 0; j < as.size(); ++j) path[i].push_back(as[j]);
      |                  ~~^~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:116:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |      if (ind[i] == path[i].size()) { com[i] = true; ++completed; break; }
      |          ~~~~~~~^~~~~~~~~~~~~~~~~
jail.cpp: In function 'll parent(ll, ll)':
jail.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18264 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 5 ms 18416 KB Output is correct
4 Correct 13 ms 18780 KB Output is correct
5 Correct 23 ms 18780 KB Output is correct
6 Correct 5 ms 18380 KB Output is correct
7 Correct 5 ms 18460 KB Output is correct
8 Correct 6 ms 18524 KB Output is correct
9 Correct 87 ms 50308 KB Output is correct
10 Correct 1214 ms 515200 KB Output is correct
11 Correct 8 ms 18520 KB Output is correct
12 Correct 33 ms 19268 KB Output is correct
13 Correct 161 ms 118100 KB Output is correct
14 Correct 155 ms 145220 KB Output is correct
15 Runtime error 1256 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18268 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 5 ms 18428 KB Output is correct
4 Incorrect 5 ms 18456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18268 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 5 ms 18428 KB Output is correct
4 Incorrect 5 ms 18456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18268 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 5 ms 18428 KB Output is correct
4 Incorrect 5 ms 18456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18268 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 5 ms 18428 KB Output is correct
4 Incorrect 5 ms 18456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18264 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct
4 Correct 4 ms 18268 KB Output is correct
5 Correct 8 ms 18524 KB Output is correct
6 Incorrect 4 ms 18268 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18264 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 5 ms 18416 KB Output is correct
4 Correct 13 ms 18780 KB Output is correct
5 Correct 23 ms 18780 KB Output is correct
6 Correct 5 ms 18380 KB Output is correct
7 Correct 5 ms 18460 KB Output is correct
8 Correct 6 ms 18524 KB Output is correct
9 Correct 87 ms 50308 KB Output is correct
10 Correct 1214 ms 515200 KB Output is correct
11 Correct 8 ms 18520 KB Output is correct
12 Correct 33 ms 19268 KB Output is correct
13 Correct 161 ms 118100 KB Output is correct
14 Correct 155 ms 145220 KB Output is correct
15 Runtime error 1256 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -