답안 #965344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965344	2024-04-18T11:04:26 Z	Alkaser_ID	Jail (JOI22_jail)	C++17	0 / 100	1256 ms	1048576 KB

jail

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-