oj.uz

Submission #552259

# Submission time Handle Problem Language Result Execution time Memory
552259 2022-04-22T23:53:17 Z LucaDantas Jail (JOI22_jail) C++17
5 / 100
 1180 ms 342640 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 120010, logn = 20;

struct Top {
	vector<int> g[(2*logn+1) * maxn];
	int ingrau[(2*logn+1) * 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]);
		}
	}
	// printf("idx %d\n", idx);
}

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:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
jail.cpp:130:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
jail.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |    scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
      |    ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:137:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   int m; scanf("%d", &m);
      |          ~~~~~^~~~~~~~~~
jail.cpp:139:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 118612 KB Output is correct
2 Correct 54 ms 118620 KB Output is correct
3 Correct 64 ms 118604 KB Output is correct
4 Correct 123 ms 118900 KB Output is correct
5 Correct 189 ms 118832 KB Output is correct
6 Correct 62 ms 119172 KB Output is correct
7 Correct 64 ms 119116 KB Output is correct
8 Correct 68 ms 119096 KB Output is correct
9 Correct 328 ms 130100 KB Output is correct
10 Correct 723 ms 323276 KB Output is correct
11 Correct 85 ms 118828 KB Output is correct
12 Correct 209 ms 119816 KB Output is correct
13 Correct 866 ms 328656 KB Output is correct
14 Correct 574 ms 329184 KB Output is correct
15 Correct 790 ms 330656 KB Output is correct
16 Correct 1180 ms 342640 KB Output is correct
17 Correct 768 ms 333044 KB Output is correct
18 Correct 831 ms 332124 KB Output is correct
19 Correct 782 ms 332848 KB Output is correct
20 Correct 693 ms 333096 KB Output is correct
21 Correct 610 ms 332404 KB Output is correct
22 Correct 537 ms 328264 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 118728 KB Output is correct
2 Correct 57 ms 118604 KB Output is correct
3 Correct 63 ms 119052 KB Output is correct
4 Correct 64 ms 119164 KB Output is correct
5 Correct 65 ms 119116 KB Output is correct
6 Correct 66 ms 119172 KB Output is correct
7 Correct 67 ms 119072 KB Output is correct
8 Correct 74 ms 119404 KB Output is correct
9 Correct 66 ms 119164 KB Output is correct
10 Correct 64 ms 119168 KB Output is correct
11 Correct 64 ms 119076 KB Output is correct
12 Incorrect 61 ms 119072 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 118728 KB Output is correct
2 Correct 57 ms 118604 KB Output is correct
3 Correct 63 ms 119052 KB Output is correct
4 Correct 64 ms 119164 KB Output is correct
5 Correct 65 ms 119116 KB Output is correct
6 Correct 66 ms 119172 KB Output is correct
7 Correct 67 ms 119072 KB Output is correct
8 Correct 74 ms 119404 KB Output is correct
9 Correct 66 ms 119164 KB Output is correct
10 Correct 64 ms 119168 KB Output is correct
11 Correct 64 ms 119076 KB Output is correct
12 Incorrect 61 ms 119072 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 118728 KB Output is correct
2 Correct 57 ms 118604 KB Output is correct
3 Correct 63 ms 119052 KB Output is correct
4 Correct 64 ms 119164 KB Output is correct
5 Correct 65 ms 119116 KB Output is correct
6 Correct 66 ms 119172 KB Output is correct
7 Correct 67 ms 119072 KB Output is correct
8 Correct 74 ms 119404 KB Output is correct
9 Correct 66 ms 119164 KB Output is correct
10 Correct 64 ms 119168 KB Output is correct
11 Correct 64 ms 119076 KB Output is correct
12 Incorrect 61 ms 119072 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 118728 KB Output is correct
2 Correct 57 ms 118604 KB Output is correct
3 Correct 63 ms 119052 KB Output is correct
4 Correct 64 ms 119164 KB Output is correct
5 Correct 65 ms 119116 KB Output is correct
6 Correct 66 ms 119172 KB Output is correct
7 Correct 67 ms 119072 KB Output is correct
8 Correct 74 ms 119404 KB Output is correct
9 Correct 66 ms 119164 KB Output is correct
10 Correct 64 ms 119168 KB Output is correct
11 Correct 64 ms 119076 KB Output is correct
12 Incorrect 61 ms 119072 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 118716 KB Output is correct
2 Correct 59 ms 118708 KB Output is correct
3 Correct 64 ms 118724 KB Output is correct
4 Correct 59 ms 118688 KB Output is correct
5 Correct 81 ms 118740 KB Output is correct
6 Incorrect 60 ms 119100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 118612 KB Output is correct
2 Correct 54 ms 118620 KB Output is correct
3 Correct 64 ms 118604 KB Output is correct
4 Correct 123 ms 118900 KB Output is correct
5 Correct 189 ms 118832 KB Output is correct
6 Correct 62 ms 119172 KB Output is correct
7 Correct 64 ms 119116 KB Output is correct
8 Correct 68 ms 119096 KB Output is correct
9 Correct 328 ms 130100 KB Output is correct
10 Correct 723 ms 323276 KB Output is correct
11 Correct 85 ms 118828 KB Output is correct
12 Correct 209 ms 119816 KB Output is correct
13 Correct 866 ms 328656 KB Output is correct
14 Correct 574 ms 329184 KB Output is correct
15 Correct 790 ms 330656 KB Output is correct
16 Correct 1180 ms 342640 KB Output is correct
17 Correct 768 ms 333044 KB Output is correct
18 Correct 831 ms 332124 KB Output is correct
19 Correct 782 ms 332848 KB Output is correct
20 Correct 693 ms 333096 KB Output is correct
21 Correct 610 ms 332404 KB Output is correct
22 Correct 537 ms 328264 KB Output is correct
23 Correct 57 ms 118728 KB Output is correct
24 Correct 57 ms 118604 KB Output is correct
25 Correct 63 ms 119052 KB Output is correct
26 Correct 64 ms 119164 KB Output is correct
27 Correct 65 ms 119116 KB Output is correct
28 Correct 66 ms 119172 KB Output is correct
29 Correct 67 ms 119072 KB Output is correct
30 Correct 74 ms 119404 KB Output is correct
31 Correct 66 ms 119164 KB Output is correct
32 Correct 64 ms 119168 KB Output is correct
33 Correct 64 ms 119076 KB Output is correct
34 Incorrect 61 ms 119072 KB Output isn't correct
35 Halted 0 ms 0 KB -