Submission #544497

#	Time	Username	Problem	Language	Result	Execution time	Memory
544497		model_code	Jail (JOI22_jail)	C++17	100 / 100	1710 ms	446332 KiB

jail

#include <bits/stdc++.h>
using namespace std;

// Input & Graph
int N, A[200009], B[200009];
int M, S[200009], T[200009];
int SVal[200009], TVal[200009];
int Sidx[200009][20];
int Tidx[200009][20];
vector<int> G[200009];
vector<int> H[9000009];

// Others
int NumVertices;
int parent[200009][20], dist[200009];
int indeg[9000009];
vector<int> tmp, Path;

void AllInit(int N, int M, int Verts) {
	for (int i = 0; i < N; i++) G[i].clear();
	for (int i = 0; i < Verts; i++) H[i].clear();
	NumVertices = 0;
}

void dfs_init(int pos, int par, int dep) {
	dist[pos] = dep;
	for (int to : G[pos]) {
		if (to == par) continue;
		parent[to][0] = pos;
		dfs_init(to, pos, dep + 1);
	}
}

int prevs(int pos, int x) {
	for (int i = 19; i >= 0; i--) {
		if (x >= (1 << i)) { pos = parent[pos][i]; x -= (1 << i); }
	}
	return pos;
}

int GetLCA(int u, int v) {
	if (dist[u] > dist[v]) swap(u, v);
	v = prevs(v, dist[v] - dist[u]);
	if (u == v) return u;
	for (int i = 19; i >= 0; i--) {
		if (parent[u][i] == parent[v][i]) continue;
		u = parent[u][i];
		v = parent[v][i];
	}
	return parent[u][0];
}

bool TopologicalSort() {
	for (int i = 0; i < NumVertices; i++) indeg[i] = 0;
	for (int i = 0; i < NumVertices; i++) {
		for (int j : H[i]) indeg[j] += 1;
	}
	
	queue<int> Q;
	for (int i = 0; i < NumVertices; i++) {
		if (indeg[i] == 0) Q.push(i);
	}
	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int to : H[pos]) {
			indeg[to] -= 1;
			if (indeg[to] == 0) Q.push(to);
		}
	}
	
	for (int i = 0; i < NumVertices; i++) {
		if (indeg[i] != 0) return false;
	}
	return true;
}

void AddS(int pos, int x, int base) {
	for (int i = 19; i >= 0; i--) {
		if (x < (1 << i)) continue;
		H[Sidx[pos][i]].push_back(base);
		x -= (1 << i);
		pos = parent[pos][i];
	}
}

void AddT(int pos, int x, int base) {
	for (int i = 19; i >= 0; i--) {
		if (x < (1 << i)) continue;
		H[base].push_back(Tidx[pos][i]);
		x -= (1 << i);
		pos = parent[pos][i];
	}
}

bool GetAnswer(int NN, vector<int> AA, vector<int> BB, int MM, vector<int> SS, vector<int> TT) {
	AllInit(N, M, NumVertices);
	N = NN;
	for (int i = 0; i < N - 1; i++) A[i] = AA[i] - 1;
	for (int i = 0; i < N - 1; i++) B[i] = BB[i] - 1;
	M = MM;
	for (int i = 0; i < M; i++) S[i] = SS[i] - 1;
	for (int i = 0; i < M; i++) T[i] = TT[i] - 1;
	
	// Step #1. Obvious Case
	for (int i = 0; i < N; i++) SVal[i] = -1;
	for (int i = 0; i < N; i++) TVal[i] = -1;
	for (int i = 0; i < M; i++) {
		if (SVal[S[i]] != -1) return false;
		else SVal[S[i]] = i;
		if (TVal[T[i]] != -1) return false;
		else TVal[T[i]] = i;
	}
	
	// Step #2. Make Graph
	for (int i = 0; i < N - 1; i++) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	
	// Step #3. Get LCA
	dfs_init(0, -1, 0);
	parent[0][0] = -1;
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < N; j++) {
			if (parent[j][i] == -1) parent[j][i + 1] = -1;
			else parent[j][i + 1] = parent[parent[j][i]][i];
		}
	}
	
	// Step #4. Init Sparse Table
	NumVertices = M;
	for (int i = 0; i < 20; i++) {
		for (int j = 0; j < N; j++) { NumVertices += 1; Sidx[j][i] = NumVertices; }
	}
	for (int i = 0; i < 20; i++) {
		for (int j = 0; j < N; j++) { NumVertices += 1; Tidx[j][i] = NumVertices; }
	}
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < N; j++) {
			int idx1 = Sidx[j][i + 1];
			int idx2 = Tidx[j][i + 1];
			int pars = parent[j][i];
			H[Sidx[j][i]].push_back(idx1);
			H[idx2].push_back(Tidx[j][i]);
			if (pars != -1) {
				H[Sidx[pars][i]].push_back(idx1);
				H[idx2].push_back(Tidx[pars][i]);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		int idx1 = Sidx[i][0];
		int idx2 = Tidx[i][0];
		if (SVal[i] != -1) H[SVal[i]].push_back(idx1);
		if (TVal[i] != -1) H[idx2].push_back(TVal[i]);
	}
	
	// Step #5. Add Edges
	for (int i = 0; i < M; i++) {
		int LCA = GetLCA(S[i], T[i]);
		int LengthS = dist[S[i]] - dist[LCA];
		int LengthT = dist[T[i]] - dist[LCA];
		if (LengthS >= 2) {
			AddS(parent[S[i]][0], LengthS - 1, i);
			AddT(parent[S[i]][0], LengthS - 1, i);
		}
		if (LengthT >= 2) {
			AddS(parent[T[i]][0], LengthT - 1, i);
			AddT(parent[T[i]][0], LengthT - 1, i);
		}
		vector<int> Cand = {S[i], T[i], LCA};
		for (int j : Cand) {
			if (SVal[j] != i && SVal[j] != -1) H[SVal[j]].push_back(i);
			if (TVal[j] != i && TVal[j] != -1) H[i].push_back(TVal[j]);
		}
	}
	
	// Step #6. Topological Sort
	bool ret = TopologicalSort();
	return ret;
}

int main() {
	int Q;
	cin >> Q;
	for (int testcase = 1; testcase <= Q; testcase++) {
		// Input
		int NN, MM;
		cin >> NN;
		vector<int> AA(NN - 1, 0), BB(NN - 1, 0);
		for (int i = 0; i < NN - 1; i++) cin >> AA[i] >> BB[i];
		cin >> MM;
		vector<int> SS(MM, 0), TT(MM, 0);
		for (int i = 0; i < MM; i++) cin >> SS[i] >> TT[i];
		
		// Output
		bool FinalAns = GetAnswer(NN, AA, BB, MM, SS, TT);
		if (FinalAns == true) cout << "Yes" << endl;
		if (FinalAns == false) cout << "No" << endl;
	}
	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