Submission #587496

#	Time	Username	Problem	Language	Result	Execution time	Memory
587496		penguinhacker	Jail (JOI22_jail)	C++17	49 / 100	5065 ms	255568 KiB

jail

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=120000;
int n, m, s[mxN], t[mxN], cnt[mxN];
vector<int> path[mxN], adj[mxN];
bool vis[mxN];

bool dfs(int u, int p, int i) {
	path[i].push_back(u);
	if (u==t[i])
		return 1;
	for (int v : adj[u])
		if (v!=p&&dfs(v, u, i))
			return 1;
	path[i].pop_back();
	return 0;
}

void solve() {
	cin >> n;
	for (int i=0; i<n; ++i) {
		adj[i].clear();
		path[i].clear();
	}
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin >> m;
	for (int i=0; i<m; ++i) {
		cin >> s[i] >> t[i], --s[i], --t[i];
		assert(dfs(s[i], -1, i));
	}
	memset(cnt, 0, 4*n);
	memset(vis, 0, m);
	for (int i=0; i<m; ++i)
		for (int j : path[i])
			++cnt[j];
	for (int rep=0; rep<m; ++rep) {
		bool found=0;
		for (int i=0; i<m; ++i) {
			if (vis[i]||cnt[t[i]]>1)
				continue;
			bool ok=1;
			for (int j=0; j<m; ++j)
				if (!vis[j]&&i!=j&&find(path[i].begin(), path[i].end(), s[j])!=path[i].end()) {
					ok=0;
					break;
				}
			if (ok) {
				vis[i]=1;
				found=1;
				for (int j : path[i])
					--cnt[j];
				break;
			}
		}
		if (!found) {
			cout << "No\n";
			return;
		}
	}
	cout << "Yes\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/string.h:495,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from jail.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'void solve()' at jail.cpp:41:8:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified size between 18446744071562067968 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23