Submission #1130066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130066		beaboss	Jail (JOI22_jail)	C++20	49 / 100	2791 ms	1114112 KiB

jail

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
const int N = 12e4;
vi adj[N];
vi dag[N];
bool vis[N];
int in[N], out[N];
int st[N], en[N], indeg[N];
int timer = 0;
int par[N];
void dfs(int cur, int p = 0) {
	par[cur]=p;
	in[cur] = timer++;
	for (auto val: adj[cur]) {
		if (val != p) dfs(val, cur);
	}
	out[cur]=timer;
}

bool is_anc(int a, int b) {
	return in[a] <= in[b] && out[a] >= out[b];
}

void upd_dag(int ind, int start, int end) {
	// cout << start << end << endl;
	vi path = {start};
	while (!is_anc(start, end)) {
		// cout << start << endl;
		start=par[start];
		path.pb(start);
	}
	// cout << start << end << par[end] << endl;
	while (end != start) {
		// cout << end << endl;
		path.pb(end);
		end=par[end];
	}
	for (auto x: path) {
		if (en[x] && ind != en[x]) {
			indeg[en[x]]++;
			// cout << ind << ' ' << en[x] << endl;

			dag[ind].pb(en[x]);
		}
		if (st[x] && ind != st[x]) {
			indeg[ind]++;
			// cout << st[x] << ' ' << ind << endl;
			dag[st[x]].pb(ind);
		}
	}
	// cout << endl;
}

bool trav_dag(int cur) {
	// cout << cur << endl;
	if (vis[cur]) return false;
	vis[cur]=true;
	bool fail=false;
	for (auto val: dag[cur]) {
		indeg[val]--;
		if (indeg[val] == 0) fail |= trav_dag(val);
	}
	return fail;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;
		FOR(i, 1, n+1) {
			adj[i].clear();
			st[i] = en[i]=0;
			dag[i].clear();
			vis[i]=false;
			indeg[i]=0;
			
		}

		FOR(i, 1, n) {
			int x, y;
			cin >> x >> y;
			adj[x].pb(y);
			adj[y].pb(x);
		}

		dfs(1);
		int m;
		cin >> m;

		vpii paths(m);

		FOR(i, 0, m) {
			cin >> paths[i].f >> paths[i].s;
			st[paths[i].f]=i+1;
			en[paths[i].s]=i+1;
		}
		// cout << 'd' << endl;
		FOR(i, 0, paths.size())
			upd_dag(i + 1, paths[i].f, paths[i].s);
		bool works=true;
		// cout << 'd' << endl;
		FOR(i, 1, m+1) {
			if (indeg[i] == 0) {
				// cout << i << endl;
				works &= !trav_dag(i);
			}
		}
		FOR(i, 1, m+1) works &= vis[i];
		if (works) cout << "Yes" << endl;
		else cout << "No" << endl;

	}

}

• 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