Submission #1143791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143791		monkey133	Jail (JOI22_jail)	C++20	100 / 100	1551 ms	522084 KiB

jail

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, m, lab;
vector<ll> adj[5000005], adj2[5000005];
ll st[5000005],fi[5000005];
ll twok[500005][25], id1[500005][25], id2[500005][25], dep[5000005], status[5000005];

ll kpar(ll x, ll k)
{
	for (ll i=0; i<17; ++i) if ((1LL << i)&k) x = twok[x][i];
	return x;
}

ll lca(ll x, ll y)
{
	if (x==y) return x;
	if (dep[x] < dep[y]) swap(x, y);
	x = kpar(x, dep[x] - dep[y]);
	if (x==y) return x;
	for (ll i=16; i>=0; --i)
	{
		if (twok[x][i]==0 || twok[y][i]==0 || twok[x][i]==twok[y][i]) continue;
		x = twok[x][i], y = twok[y][i];
	}
	return twok[x][0];
}

void dfs(ll x = 1, ll p = -1)
{
	for (ll k=1; k<17; ++k)
	{
		twok[x][k] = twok[twok[x][k-1]][k-1];
		id1[x][k] = ++lab;
		id2[x][k] = ++lab;
		// start : go up
		if (id1[x][k-1] > 0) adj2[id1[x][k-1]].pb(id1[x][k]);
		if (id1[twok[x][k-1]][k-1] > 0) adj2[id1[twok[x][k-1]][k-1]].pb(id1[x][k]);
		// end : go down
		if (id2[x][k-1] > 0) adj2[id2[x][k]].pb(id2[x][k-1]);
		if (id2[twok[x][k-1]][k-1] > 0) adj2[id2[x][k]].pb(id2[twok[x][k-1]][k-1]);
	}
	for (ll u: adj[x]) if (u!=p) 
	{
		dep[u] = dep[x] + 1;
		twok[u][0] = x;
		dfs(u, x);
	}
}

void add_dir(ll from , ll to, ll idx)
{
	ll k = dep[from] - dep[to] + 1;
	ll now = from;
	for (ll i=16; i>=0; --i) if ((1LL << i) & k)
	{
		if (id1[now][i]) adj2[id1[now][i]].pb(idx);
		now = twok[now][i];
	}
}

void add_rev(ll from , ll to, ll idx)
{
	ll k = dep[from] - dep[to] + 1;
	ll now = from;
	for (ll i=16; i>=0; --i) if ((1LL << i) & k)
	{
		if (id2[now][i]) adj2[idx].pb(id2[now][i]);
		now = twok[now][i];
	}
}

bool fail = false;
void topo(ll node)
{
	if (status[node]==2) return;
	if (status[node]==1) {fail = true; return;}
	status[node]=1;
	for (ll x: adj2[node])
	{
		topo(x);
		if (fail) break;
	}
	status[node]=2;
}




void solve()
{
	cin >> n;
	for (ll i=0; i<n-1; ++i)
	{
		ll u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	cin >> m;
	lab = m;
	for (ll i=1; i<=m; ++i) 
	{
		cin >> st[i] >> fi[i];
		id1[st[i]][0] = i;
		id2[fi[i]][0] = i;
	}
	// decompose every path into log(n) segment  + twok decomposition
	dfs();
	if (lab >= 5000000) cout << 0 << endl;
	// add edges
	for (ll i=1; i<=m; ++i)
	{
		ll lc = lca(st[i], fi[i]);
		// connect to other st[i] 
		// *excluding st[i] -> st[i] to prevent self-loop
		if (st[i]==lc) add_dir(fi[i], kpar(fi[i],  dep[fi[i]] - dep[st[i]]-1), i);
		else add_dir(twok[st[i]][0], lc, i), add_dir(fi[i], lc, i);
		// connect to other fi[i]
		if (fi[i]==lc) add_rev(st[i], kpar(st[i],  dep[st[i]] - dep[fi[i]]-1), i);
		else add_rev(st[i], lc, i), add_rev(twok[fi[i]][0], lc, i);
	}
	for (ll i=1; i<=m; ++i) topo(i);
	if (fail) cout << "No\n";
	else cout << "Yes\n";
	for (ll i=1; i<=n; ++i) adj[i].clear(), dep[i] = 0;
	for (ll i=1; i<=lab; ++i) adj2[i].clear(), status[i] = 0;
	for (ll i=1; i<=n; ++i)  for (ll k=0; k<20; ++k) twok[i][k] = id1[i][k] = id2[i][k] = 0;
	fail = 0;
	
}
int main()
{
	ll q;
	cin >> q;
	while (q--) solve();
	return 0;
}

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