oj.uz

Submission #660209

# Submission time Handle Problem Language Result Execution time Memory
660209 2022-11-21T06:54:30 Z Sohsoh84 Jail (JOI22_jail) C++17
0 / 100
 511 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 12e5 + 10;
const ll LOG = 20;

int n, m, t, tin[MAXN], tout[MAXN], S[MAXN], T[MAXN], Par[MAXN][LOG], col[MAXN * LOG * 2],
    tn, gin[MAXN][LOG], gout[MAXN][LOG], H[MAXN], ind_S[MAXN], ind_T[MAXN];
vector<int> adj[MAXN], G[MAXN * LOG * 2];
bool flag = false;

inline void clear() {
	for (int i = 0; i < n + 5; i++) {
		tin[i] = tout[i] = S[i] = T[i] = H[i] = ind_S[i] = ind_T[i] = 0;
		memset(Par[i], 0, sizeof Par[i]);
		memset(gin[i], 0, sizeof gin[i]);
		memset(gout[i], 0, sizeof gout[i]);
		adj[i].clear();
	}
	
	for (int i = 0; i < tn + 10; i++) {
		col[i] = 0;
		G[i].clear();
	}

	n = m = t = tn = 0;
	flag = false;
}

void dfs(int v, int p) {
	H[v] = H[p] + 1;
	tin[v] = ++t;
	Par[v][0] = p;

	for (int u : adj[v])
		if (u != p)
			dfs(u, v);

	tout[v] = t;
}

inline bool par(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

inline int LCA(int u, int v) {
	if (par(u, v)) return u;
	if (par(v, u)) return v;

	for (int i = LOG - 1; i >= 0; i--)
		if (Par[u][i] != 0 && !par(Par[u][i], v))
			u = Par[u][i];

	return Par[u][0];
}

inline int k_par(int v, int k) {
	for (int i = LOG - 1; i >= 0; i--)
		if (k & (1 << i))
			v = Par[v][i];
	return v;
}

inline vector<pll> decomp(int v, int h) {
	vector<pll> ans;
	for (int i = LOG - 1; i >= 0; i--) {
		if (h & (1 << i)) {
			ans.push_back({v, i});
			v = Par[v][i];
		}
	}

	return ans;
}

void cyc(int v) {
	col[v] = 1;
	for (int u : G[v]) {
		if (!col[u]) cyc(u);
		else if (col[u] == 1) flag = true;
	}

	col[v] = 2;
}

inline vector<pll> path_decomp(int u, int v) { // -u
	if (u == v) return {};
	if (par(u, v)) u = k_par(v, H[v] - H[u] - 1);
	else u = Par[u][0];

	int lca = LCA(u, v);
	vector<pll> ans = decomp(u, H[u] - H[lca] + 1), tans = decomp(v, H[v] - H[lca] + 1);
	for (auto e : tans) ans.push_back(e);

	return ans;
}

inline int solve() {	
	clear();

	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> S[i] >> T[i];
		ind_S[S[i]] = i;
		ind_T[T[i]] = i;
	}

	dfs(1, 0);
	for (int v = 1; v <= n; v++) {
		gin[v][0] = ind_S[v];	
		gout[v][0] = ind_T[v];	
	}

	tn = n;

	for (int i = 1; i < LOG; i++) {
		for (int v = 1; v <= n; v++) {
			int p = Par[v][i - 1];
			Par[v][i] = Par[p][i - 1];

			if (gin[v][i - 1] || gin[p][i - 1]) {
				tn++;
				if (gin[v][i - 1]) G[gin[v][i - 1]].push_back(tn);
				if (gin[p][i - 1]) G[gin[p][i - 1]].push_back(tn);

				gin[v][i] = tn;
			} 

			if (gout[v][i - 1] || gout[p][i - 1]) {
				tn++;
				if (gout[v][i - 1]) G[tn].push_back(gout[v][i - 1]);
				if (gout[p][i - 1]) G[tn].push_back(gout[p][i - 1]);
				
				gout[v][i] = tn;
			}
		}
	}

	// check 0
	for (int i = 1; i <= m; i++) {
		vector<pll> svec = path_decomp(S[i], T[i]), tvec = path_decomp(T[i], S[i]);
		for (auto [v, j] : svec) {
			if (gin[v][j]) 
				G[gin[v][j]].push_back(i);
		}

		for (auto [v, j] : tvec) {
			if (gout[v][j])
				G[i].push_back(gout[v][j]);
		}
	}

	for (int i = 1; i <= tn; i++) {
		if (!col[i])
			cyc(i);
	}

	cout << (flag ? "No" : "Yes") << endl;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q;
	cin >> q;
	while (q--) solve();
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 455 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 511 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 511 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 511 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 511 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 442 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 455 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -