oj.uz

Submission #617997

# Submission time Handle Problem Language Result Execution time Memory
617997 2022-08-01T18:54:03 Z patrikpavic2 Jail (JOI22_jail) C++17
0 / 100
 59 ms 107820 KB 
#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) 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];
		}
	}
	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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 107784 KB Output is correct
2 Correct 53 ms 107740 KB Output is correct
3 Incorrect 51 ms 107720 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107804 KB Output is correct
2 Incorrect 51 ms 107740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107804 KB Output is correct
2 Incorrect 51 ms 107740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107804 KB Output is correct
2 Incorrect 51 ms 107740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107804 KB Output is correct
2 Incorrect 51 ms 107740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 107772 KB Output is correct
2 Correct 51 ms 107820 KB Output is correct
3 Correct 53 ms 107780 KB Output is correct
4 Incorrect 59 ms 107792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 107784 KB Output is correct
2 Correct 53 ms 107740 KB Output is correct
3 Incorrect 51 ms 107720 KB Output isn't correct
4 Halted 0 ms 0 KB -