Submission #561521

#	Time	Username	Problem	Language	Result	Execution time	Memory
561521		8e7	Jail (JOI22_jail)	C++17	100 / 100	1050 ms	288124 KiB

jail

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], gout[18 * maxn], gin[18 * maxn];
int anc[18][maxn], dep[maxn], deg[maxn], dout[18 * maxn], din[18 * maxn], core[maxn], cors[maxn];
bool vin[18 * maxn], vout[18 * maxn];
pii ed[maxn];
void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;	
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
		}
	}
}
int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) a = anc[cnt][a];
		hdif >>= 1, cnt++;
	}
	if (a == b) return a;
	for (int i = 17;i >= 0;i--) {
		if (anc[i][a] != anc[i][b]) {
			a = anc[i][a], b = anc[i][b];
		}
	}
	return anc[0][a];
}
int getdis(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
bool onl(int u, int v, int x) {
	return getdis(u, v) == getdis(u, x) + getdis(x, v);
}
void addedge (int ix, int jx, int iy, int jy, int type){
	if (type) {
		gout[ix * maxn + jx].push_back(iy * maxn + jy);
		dout[iy*maxn + jy]++;
	} else {
		gin[ix * maxn + jx].push_back(iy * maxn + jy);
		din[iy*maxn + jy]++;
	}
}


void datag(int u, int x, int dis, int type) { //0: in, 1:out
	if (dis <= 0) return;
	int cnt = 0;
	while (dis) {
		if (dis & 1) {
			if (type) {
				addedge(0, u, cnt, x, 1);
			} else {
				addedge(cnt, x, 0, u, 0);
			}
			x = anc[cnt][x];
		}
		dis >>= 1, cnt++;	
	}
}

int main() {
	io
	int T;
	cin >> T;
	while (T--) {

		int n;
		cin >> n;
		for (int i = 0;i < 18;i++) {
			for (int j = 1;j <= n;j++) {
				din[i * maxn + j] = 0;
				dout[i * maxn + j] = 0;
				gin[i * maxn + j].clear();
				gout[i * maxn + j].clear();
				vin[i * maxn + j] = vout[i * maxn + j] = 0;
			}
		}
		for (int i = 1;i <= n;i++) {
			adj[i].clear();
			deg[i] = 0;
			core[i] = cors[i] = 0;
		}
		for (int i = 0;i < n - 1;i++) {
			int u,v;
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		dfs(1, 0, 0);
		for (int i = 1;i < 18;i++) {
			for (int j = 1;j <= n;j++) {
				anc[i][j] = anc[i-1][anc[i-1][j]];

				addedge(i-1, j, i, j, 0);
				addedge(i-1, anc[i-1][j], i, j, 0);
				addedge(i, j, i-1, j, 1);
				addedge(i, j, i-1, anc[i-1][j], 1);
			}
		}
		int m;
		cin >> m;
		for (int i = 1;i <= m;i++) {
			int u, v;
			cin >> u >> v;
			int l = lca(u, v);	
			datag(v, u, dep[u] - dep[l], 0);	
			datag(v, anc[0][v], dep[v] - dep[l], 0);	
			datag(u, anc[0][u], dep[u] - dep[l], 1);
			datag(u, v, dep[v] - dep[l], 1);

			core[v] = i, cors[u] = i;
			ed[i] = {u, v};
		}
		queue<int> que;
		for (int i = 1;i <= n;i++) {
			if (!core[i]) que.push(i);
		}	
		for (int i = 1;i <= n;i++) que.push(-(17 * maxn + i));
		int cnt = 0;
		while (que.size()) {
			int cur = que.front();que.pop();
			if (cur > 0) {
				vin[cur] = 1;
				//debug(cur / maxn, cur % maxn);
				if (cur < maxn && core[cur]) cnt++;
				for (int v:gin[cur]) {
					//debug("in", cur, v);
					if (--din[v] == 0) {
						if (!(v < maxn && core[v] && dout[ed[core[v]].ff] > 0)) {
							if (!vin[v]) que.push(v), vin[v] = 1;
						}
						if (v < maxn && core[v]) {
							int p = ed[core[v]].ff;
							if (dout[p] == 0 && !vout[p]) que.push(-p), vout[p] = 1;
						}
					}
				}
			} else {
				//debug("out", (-cur) / maxn, (-cur) % maxn);
				vout[-cur] = 1;
				for (int v:gout[-cur]) {
					//debug("out", -cur, v);
					if (--dout[v] == 0) {
						if (!(v < maxn && cors[v] && din[ed[cors[v]].ss] > 0)) {
							if (!vout[v]) que.push(-v), vout[v] = 1;
						}
						if (v < maxn && cors[v]) {
							int p = ed[cors[v]].ss;	
							if (din[p] == 0 && !vin[p]) que.push(p), vin[p] = 1;
						}
					}
				}
			}
		}
		
		debug(cnt);	
		cout << (cnt == m ? "Yes" : "No") << "\n";	
	}
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
jail.cpp:177:3: note: in expansion of macro 'debug'
  177 |   debug(cnt);
      |   ^~~~~

• 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