oj.uz

Submission #552234

# Submission time Handle Problem Language Result Execution time Memory
552234 2022-04-22T20:27:38 Z LucaDantas Jail (JOI22_jail) C++17
0 / 100
 360 ms 368596 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 120010, logn = 21;

struct Top {
	vector<int> g[logn * maxn];
	int ingrau[logn * maxn];
	queue<int> q;
	void add_edge(int a, int b) {
		// if(a == b) return; // só colocar esse if não funciona mais já que agr eu tenho arestas virtuais do binary lifting
		// printf("adding %d -> %d\n", a, b);
		ingrau[b]++;
		g[a].push_back(b);
	}
	void clear(int n) {
		for(int i = 0; i <= n; i++)
			ingrau[i] = 0, g[i].clear();
		while(q.size())
			q.pop();
	}
	bool dag(int n) {
		for(int i = 1; i <= n; i++)
			if(!ingrau[i]) q.push(i);
		int vis = 0;
		while(q.size()) {
			int u = q.front(); q.pop();
			++vis;
			for(int v : g[u])
				if(!(--ingrau[v]))
					q.push(v);
		}
		return vis == n;
	}
} top;

int p[maxn][logn], depth[maxn], comeca[maxn][logn], termina[maxn][logn]; // salvo o indice do cara que comeca e termina em mim caso exista
int s[maxn], t[maxn];
int idx;
bool mark[maxn];
vector<int> g[maxn];

void dfs(int u) {
	for(int v : g[u]) if(v != p[u][0]) {
		p[v][0] = u;
		depth[v] = depth[u] + 1;
		dfs(v);
	}
}

void build(int n) {
	idx = n;
	for(int i = 1; i <= n; i++)
		comeca[i][0] = ++idx, termina[i][0] = ++idx;
	for(int l = 1; l < logn; l++) {
		for(int i = 1; i <= n; i++) {
			comeca[i][l] = ++idx, termina[i][l] = ++idx;
			p[i][l] = p[p[i][l-1]][l-1];

			top.add_edge(comeca[i][l-1], comeca[i][l]);
			if(p[i][l-1])
				top.add_edge(comeca[p[i][l-1]][l-1], comeca[i][l]);

			top.add_edge(termina[i][l], termina[i][l-1]);
			if(p[i][l-1])
				top.add_edge(termina[i][l], termina[p[i][l-1]][l-1]);
		}
	}
}

void go(int id) {
	int a = s[id], b = t[id];
	// printf("comeca %d %d\n", a, b);
	// a != b sempre
	
	top.add_edge(comeca[b][0], id);
	top.add_edge(id, termina[a][0]);

	bool foi = 0;
	if(depth[a] == depth[b]) {
		foi = 1;
		a = p[a][0];
		b = p[b][0];
	} else {
		if(depth[a] < depth[b])
			swap(a, b); // a é o mais fundo
		a = p[a][0]; // não quero que ele crie uma aresta dele pra ele mesmo, então eu crio subo um andar do mais baixo sem fazer o upd
	}

	for(int l = logn-1; l >= 0; l--)
		if(depth[a] - (1 << l) >= depth[b]) // comeca[a][l] e termina[a][l] não incluem p[a][l] no seu intervalo: [a, p[a][l][
			top.add_edge(comeca[a][l], id), top.add_edge(id, termina[a][l]), a = p[a][l];

	// printf("primeira %d %d\n", a, b);
	if(a == b) return;

	if(!foi) {
		b = p[b][0]; // não quero que o b crie uma aresta pra ele mesmo então eu também subo
		top.add_edge(comeca[a][0], id), top.add_edge(id, termina[a][0]), a = p[a][0];
		// mas com isso também preciso subir o a pra eles ficarem no mesmo nível dnv, só que no a eu add a aresta
	}
	
	if(a == b) return;

	for(int l = logn-1; l >= 0; l--) {
		if(p[a][l] != p[b][l]) {
			top.add_edge(comeca[a][l], id), top.add_edge(id, termina[a][l]), a = p[a][l];
			top.add_edge(comeca[b][l], id), top.add_edge(id, termina[b][l]), b = p[b][l];
		}
	}
	// comeca/termina[a][1] porque eu também quero colocar o pai (lca(a,b)) que não foi contado, então pego um intervalo de tamanho 2
	top.add_edge(comeca[a][1], id), top.add_edge(id, termina[a][1]);
	top.add_edge(comeca[b][0], id), top.add_edge(id, termina[b][0]);
}

void clear(int n) {
	for(int i = 0; i <= n; i++)
		g[i].clear(), depth[i] = 0, mark[i] = 0, s[i] = 0, t[i] = 0;
	for(int i = 0; i <= n; i++)
		for(int l = 0; l < logn; l++)
			p[i][l] = comeca[i][l] = termina[i][l] = 0;
	top.clear(idx);
	idx = 0;
}

int main() {
	int q; scanf("%d", &q);
	while(q--) {
		int n; scanf("%d", &n);
		clear(n);
		for(int i = 1, a, b; i < n; i++)
			scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
		
		dfs(1); build(n);

		int m; scanf("%d", &m);
		for(int i = 1; i <= m; i++)
			scanf("%d %d", s+i, t+i), top.add_edge(i, comeca[s[i]][0]), top.add_edge(termina[t[i]][0], i);
		
		for(int i = 1; i <= m; i++)
			go(i);
		
		puts(top.dag(idx) ? "Yes" : "No");
	}
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
jail.cpp:129:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
jail.cpp:132:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |    scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
      |    ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:136:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |   int m; scanf("%d", &m);
      |          ~~~~~^~~~~~~~~~
jail.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |    scanf("%d %d", s+i, t+i), top.add_edge(i, comeca[s[i]][0]), top.add_edge(termina[t[i]][0], i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62256 KB Output is correct
2 Correct 31 ms 62304 KB Output is correct
3 Correct 30 ms 62328 KB Output is correct
4 Correct 99 ms 62548 KB Output is correct
5 Correct 177 ms 62544 KB Output is correct
6 Correct 37 ms 62784 KB Output is correct
7 Correct 39 ms 62700 KB Output is correct
8 Correct 38 ms 62676 KB Output is correct
9 Correct 310 ms 73244 KB Output is correct
10 Runtime error 360 ms 368596 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62284 KB Output is correct
2 Correct 30 ms 62292 KB Output is correct
3 Correct 39 ms 62796 KB Output is correct
4 Correct 38 ms 62684 KB Output is correct
5 Correct 38 ms 62780 KB Output is correct
6 Correct 38 ms 62800 KB Output is correct
7 Correct 38 ms 62804 KB Output is correct
8 Correct 39 ms 62692 KB Output is correct
9 Correct 39 ms 62788 KB Output is correct
10 Correct 37 ms 62804 KB Output is correct
11 Correct 37 ms 62856 KB Output is correct
12 Incorrect 34 ms 62676 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62284 KB Output is correct
2 Correct 30 ms 62292 KB Output is correct
3 Correct 39 ms 62796 KB Output is correct
4 Correct 38 ms 62684 KB Output is correct
5 Correct 38 ms 62780 KB Output is correct
6 Correct 38 ms 62800 KB Output is correct
7 Correct 38 ms 62804 KB Output is correct
8 Correct 39 ms 62692 KB Output is correct
9 Correct 39 ms 62788 KB Output is correct
10 Correct 37 ms 62804 KB Output is correct
11 Correct 37 ms 62856 KB Output is correct
12 Incorrect 34 ms 62676 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62284 KB Output is correct
2 Correct 30 ms 62292 KB Output is correct
3 Correct 39 ms 62796 KB Output is correct
4 Correct 38 ms 62684 KB Output is correct
5 Correct 38 ms 62780 KB Output is correct
6 Correct 38 ms 62800 KB Output is correct
7 Correct 38 ms 62804 KB Output is correct
8 Correct 39 ms 62692 KB Output is correct
9 Correct 39 ms 62788 KB Output is correct
10 Correct 37 ms 62804 KB Output is correct
11 Correct 37 ms 62856 KB Output is correct
12 Incorrect 34 ms 62676 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62284 KB Output is correct
2 Correct 30 ms 62292 KB Output is correct
3 Correct 39 ms 62796 KB Output is correct
4 Correct 38 ms 62684 KB Output is correct
5 Correct 38 ms 62780 KB Output is correct
6 Correct 38 ms 62800 KB Output is correct
7 Correct 38 ms 62804 KB Output is correct
8 Correct 39 ms 62692 KB Output is correct
9 Correct 39 ms 62788 KB Output is correct
10 Correct 37 ms 62804 KB Output is correct
11 Correct 37 ms 62856 KB Output is correct
12 Incorrect 34 ms 62676 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62320 KB Output is correct
2 Correct 29 ms 62348 KB Output is correct
3 Correct 30 ms 62372 KB Output is correct
4 Correct 29 ms 62344 KB Output is correct
5 Correct 57 ms 62292 KB Output is correct
6 Incorrect 34 ms 62676 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62256 KB Output is correct
2 Correct 31 ms 62304 KB Output is correct
3 Correct 30 ms 62328 KB Output is correct
4 Correct 99 ms 62548 KB Output is correct
5 Correct 177 ms 62544 KB Output is correct
6 Correct 37 ms 62784 KB Output is correct
7 Correct 39 ms 62700 KB Output is correct
8 Correct 38 ms 62676 KB Output is correct
9 Correct 310 ms 73244 KB Output is correct
10 Runtime error 360 ms 368596 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -