Submission #618002

#	Time	Username	Problem	Language	Result	Execution time	Memory
618002		patrikpavic2	Jail (JOI22_jail)	C++17	100 / 100	2191 ms	361812 KiB

jail

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 120500;
const int LOG = 17;

vector < int > v[N], poc[N], zav[N], sm[35 * N];
int n, q, st[N], en[N], bio[35 * N], dep[N], par[N][LOG];
int dp[N][LOG][2], cv[N];

void dfs(int x, int lst){
	dep[x] = dep[lst] + 1;
	par[x][0] = lst;
	for(int y : v[x])
		if(y != lst) dfs(y, x);
}

int naso = 0, node = 1;

void make_node(int i, int j, int k){
	if(dp[i][j][k]) return;
	dp[i][j][k] = node++;
	make_node(i, j - 1, k);
	make_node(par[i][j - 1], j - 1, k);
	if(!k){
		sm[dp[i][j][k]].PB(dp[i][j - 1][k]);
		sm[dp[i][j][k]].PB(dp[par[i][j - 1]][j - 1][k]);
	}
	else{
		sm[dp[i][j - 1][k]].PB(dp[i][j][k]);
		sm[dp[par[i][j - 1]][j - 1][k]].PB(dp[i][j][k]);
	}
}

int digni(int a, int k){
	for(int j = 0;j < LOG;j++)
		if(k & (1 << j)) a = par[a][j];
	return a;	
}

int lca(int a, int b){
	if(dep[a] < dep[b]) swap(a, b);
	a = digni(a, dep[a] - dep[b]);
	if(a == b) return a;
	for(int j = LOG - 1;j >= 0;j--)
		if(par[a][j] != par[b][j])
			a = par[a][j], b = par[b][j];
	return par[a][0];
}

void oznaci(int a, int b, int k, int tko){
	if(dep[a] < dep[b]) swap(a, b);
	for(int j = LOG - 1;j >= 0;j--){
		if(dep[a] - dep[b] >= (1 << j)){
			make_node(a, j, k);
			if(!k) sm[tko].PB(dp[a][j][k]);
			else sm[dp[a][j][k]].PB(tko);
			a = par[a][j];
		}
	}
	if(a == b) {
		make_node(a, 0, k);
		if(!k) sm[tko].PB(dp[a][0][k]);
		else sm[dp[a][0][k]].PB(tko);
		return;
	}
	for(int j = LOG - 1;j >= 0;j--){
		if(par[a][j] != par[b][j]){
			make_node(a, j, k); make_node(b, j, k);
			if(!k) 
				sm[tko].PB(dp[a][j][k]),
				sm[tko].PB(dp[b][j][k]);
			else 
				sm[dp[a][j][k]].PB(tko),
				sm[dp[b][j][k]].PB(tko);
			a = par[a][j], b = par[b][j];
		}
	}
	make_node(a, 1, k); make_node(b, 0, k);
	if(!k) sm[tko].PB(dp[a][1][k]), sm[tko].PB(dp[b][0][k]);
	else sm[dp[a][1][k]].PB(tko), sm[dp[b][0][k]].PB(tko);;
	return;
}

void ciklus(int x){
	if(bio[x] == 1) { naso = 1; }
	if(bio[x]) return;
	bio[x] = 1;
	for(int y : sm[x]){
		ciklus(y);
	}
	bio[x] = 2;
}

void solve(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int a, b; scanf("%d%d", &a, &b);
		v[a].PB(b);
		v[b].PB(a);
	}
	dfs(1, 1);
	for(int j = 1;j < LOG;j++){
		for(int i = 1;i <= n;i++){
			dp[i][j][0] = 0, dp[i][j][1] = 0;
			par[i][j] = par[par[i][j - 1]][j - 1];		
		}
	}
	scanf("%d", &q);
	for(int i = 0;i < q;i++){
		int a, b; scanf("%d%d", &a, &b);
		st[i] = a; en[i] = b; cv[i] = node++;
		poc[a].PB(i); zav[b].PB(i);
	}
	for(int i = 1;i <= n;i++){
		dp[i][0][0] = node++;
		dp[i][0][1] = node++;
		for(int x : poc[i])
			sm[dp[i][0][0]].PB(cv[x]);
		for(int x : zav[i])
			sm[cv[x]].PB(dp[i][0][1]);
	}
	for(int i = 0;i < q;i++){
		int a = st[i], b = en[i];
		int lc = lca(a, b);
		if(lc != a && lc != b){
			oznaci(par[a][0], b, 0, cv[i]);
			oznaci(a, par[b][0], 1, cv[i]);
		}
		else if(lc == a){
			oznaci(digni(b, dep[b] - dep[a] - 1), b, 0, cv[i]);
			oznaci(a, par[b][0], 1, cv[i]);
		}
		else{
			oznaci(par[a][0], b, 0, cv[i]);
			oznaci(a, digni(a, dep[a] - dep[b] - 1), 1, cv[i]);
		}
	}
	for(int i = 1;i < node;i++) ciklus(i);
	for(int i = 1;i < node;i++) bio[i] = 0, sm[i].clear();
	for(int i = 1;i <= n;i++) v[i].clear(), poc[i].clear(), zav[i].clear();
	printf(naso ? "No\n" : "Yes\n");
	naso = 0; node = 1;

}

int main(){
	int T; scanf("%d", &T);
	for(;T--;) solve();
	return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void solve()':
jail.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
jail.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
jail.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  int T; scanf("%d", &T);
      |         ~~~~~^~~~~~~~~~

• 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