Submission #860372

#	Time	Username	Problem	Language	Result	Execution time	Memory
860372		KiaRez	Jail (JOI22_jail)	C++17	100 / 100	1109 ms	453064 KiB

jail

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 2e5+23, lg = 18;
ll Mod = 1e9+7;
//ll Mod = 998244353;

inline ll MOD(ll a, ll mod=Mod) {
	a%=mod; (a<0)&&(a+=mod); return a;
}
inline ll max(ll a, ll b) {return (a>b ? a : b);}
inline ll min(ll a, ll b) {return (a<b ? a : b);}
inline ll abso(ll a) {return (a<0?-a:a);}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

struct Node {
	int deg;
	vector<int> adj;
	Node() {
		deg=0;
	}
} node[N*38];

int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];

void add(int v, int u) {
	if(v==0 || u==0 || v==u) return;
	node[v].adj.pb(u);
	node[u].deg++;
}

void init(int v, int p=0) {
	par[0][v]=p, h[v]=h[p]+1;

	for(int i=1; i<lg; i++) {
		par[i][v] = par[i-1][par[i-1][v]];
	}
	for(int i=0; i<lg; i++) {
		fakes[i][v] = ++cnt;
		faket[i][v] = ++cnt;
	}
	int tmp = v;
	add(faket[0][v], rt[tmp]);
	tmp = par[0][v];
	add(faket[0][v], rt[tmp]);
	
	tmp = v;
	add(rs[tmp], fakes[0][v]);
	tmp = par[0][v];
	add(rs[tmp], fakes[0][v]);

	for(int i=1; i<lg; i++) {
		add(faket[i][v], faket[i-1][v]);
		add(faket[i][v], faket[i-1][par[i-1][v]]);

		add(fakes[i-1][v], fakes[i][v]);
		add(fakes[i-1][par[i-1][v]], fakes[i][v]);
	}

	for(int u : tree[v]) {
		if(u == p) continue;
		init(u, v);
	}
}

int getPar(int v, int dist) {
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2) {
			v = par[i][v];
		}
	}
	return v;
}

int LCA(int v, int u) {
	if(h[u] < h[v]) swap(v,u);
	u = getPar(u, h[u]-h[v]);
	if(v == u) return v;

	for(int i=lg-1; i>=0; i--) {
		if(par[i][v] != par[i][u]) {
			v=par[i][v], u=par[i][u];
		}
	}
	return par[0][v];
}

void addPaths(int cnd, int v, int dist) {
	if(dist<0 || cnd==0 || v==0) return;
	//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
	if(dist == 0) {
		//add(cnd, rt[v]);
		add(rs[v], cnd);
		return;
	}
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2==1) {
			//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
			//add(cnd, faket[i][v]);
			//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
			add(fakes[i][v], cnd);
			v = par[i][v];
		}
	}
	return;
}

void addPatht(int cnd, int v, int dist) {
	if(dist<0 || cnd==0 || v==0) return;
	//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
	if(dist == 0) {
		add(cnd, rt[v]);
		return;
	}
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2==1) {
			//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
			add(cnd, faket[i][v]);
			//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
			//add(fakes[i][v], cnd);
			v = par[i][v];
		}
	}
	return;
}

void solve() {
	cin>>n;
	for(int v,u,i=1; i<n; i++) {
		cin>>v>>u;
		tree[v].pb(u); tree[u].pb(v);
	}
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>s[i]>>t[i];
		rs[s[i]] = i;
		rt[t[i]] = i;
	}
	cnt = m;

	init(1);

	for(int i=1; i<=m; i++) {
		int lca = LCA(s[i], t[i]);
		//int ff = (s[i]==lca || t[i]==lca);
		addPaths(i, par[0][s[i]], h[par[0][s[i]]] - h[lca]);
		addPatht(i, s[i], h[s[i]] - h[lca] - (t[i]==lca));

		addPaths(i, t[i], h[t[i]] - h[lca] - (s[i]==lca));
		addPatht(i, par[0][t[i]], h[par[0][t[i]]] - h[lca]);
	}

	int cnt2=0;
	queue<int> q;
	for(int i=1; i<=cnt; i++) {
		if(node[i].deg == 0) q.push(i);
	}

	while(size(q)) {
		int v = q.front();
		q.pop();
		cnt2 ++;
		for(int u : node[v].adj) {
			node[u].deg--;
			if(node[u].deg==0) {
				q.push(u);
			}
		}
	}

	//fuck(cnt); fuck(cnt2);
	if(cnt2 == cnt) cout<<"Yes\n";
	else cout<<"No\n";
}

/*
node[N*20];
int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];
*/

void reset() {
	for(int i=0; i<=n+2; i++) {
		h[i]=s[i]=t[i]=rs[i]=rt[i]=0;
		for(int j=0; j<lg; j++) {
			fakes[j][i]=faket[j][i]=0;
		}
		while(size(tree[i])) tree[i].pop_back();
	}

	for(int i=0; i<=cnt; i++) {
		node[i].deg=0;
		while(size(node[i].adj)) node[i].adj.pop_back();
	}
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>q;
	while(q--) {
		solve();
		reset();
	}

	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