oj.uz

Submission #552238

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

// só mudei a memoria, ainda vai dar wa mas quero ver o motivo do rte na sub1
constexpr int maxn = 2*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: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 124256 KB Output is correct
2 Correct 58 ms 124344 KB Output is correct
3 Correct 56 ms 124328 KB Output is correct
4 Correct 122 ms 124544 KB Output is correct
5 Correct 196 ms 124548 KB Output is correct
6 Correct 66 ms 124764 KB Output is correct
7 Correct 69 ms 124792 KB Output is correct
8 Correct 67 ms 124716 KB Output is correct
9 Correct 343 ms 135192 KB Output is correct
10 Runtime error 849 ms 666632 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 65 ms 124236 KB Output is correct
2 Correct 70 ms 124376 KB Output is correct
3 Correct 69 ms 124796 KB Output is correct
4 Correct 76 ms 124716 KB Output is correct
5 Correct 71 ms 124784 KB Output is correct
6 Correct 73 ms 124924 KB Output is correct
7 Correct 75 ms 124748 KB Output is correct
8 Correct 71 ms 124752 KB Output is correct
9 Correct 72 ms 124736 KB Output is correct
10 Correct 71 ms 124704 KB Output is correct
11 Correct 72 ms 124776 KB Output is correct
12 Incorrect 68 ms 124684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 124236 KB Output is correct
2 Correct 70 ms 124376 KB Output is correct
3 Correct 69 ms 124796 KB Output is correct
4 Correct 76 ms 124716 KB Output is correct
5 Correct 71 ms 124784 KB Output is correct
6 Correct 73 ms 124924 KB Output is correct
7 Correct 75 ms 124748 KB Output is correct
8 Correct 71 ms 124752 KB Output is correct
9 Correct 72 ms 124736 KB Output is correct
10 Correct 71 ms 124704 KB Output is correct
11 Correct 72 ms 124776 KB Output is correct
12 Incorrect 68 ms 124684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 124236 KB Output is correct
2 Correct 70 ms 124376 KB Output is correct
3 Correct 69 ms 124796 KB Output is correct
4 Correct 76 ms 124716 KB Output is correct
5 Correct 71 ms 124784 KB Output is correct
6 Correct 73 ms 124924 KB Output is correct
7 Correct 75 ms 124748 KB Output is correct
8 Correct 71 ms 124752 KB Output is correct
9 Correct 72 ms 124736 KB Output is correct
10 Correct 71 ms 124704 KB Output is correct
11 Correct 72 ms 124776 KB Output is correct
12 Incorrect 68 ms 124684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 124236 KB Output is correct
2 Correct 70 ms 124376 KB Output is correct
3 Correct 69 ms 124796 KB Output is correct
4 Correct 76 ms 124716 KB Output is correct
5 Correct 71 ms 124784 KB Output is correct
6 Correct 73 ms 124924 KB Output is correct
7 Correct 75 ms 124748 KB Output is correct
8 Correct 71 ms 124752 KB Output is correct
9 Correct 72 ms 124736 KB Output is correct
10 Correct 71 ms 124704 KB Output is correct
11 Correct 72 ms 124776 KB Output is correct
12 Incorrect 68 ms 124684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 124304 KB Output is correct
2 Correct 64 ms 124260 KB Output is correct
3 Correct 65 ms 124268 KB Output is correct
4 Correct 73 ms 124308 KB Output is correct
5 Correct 91 ms 124480 KB Output is correct
6 Incorrect 69 ms 124760 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 124256 KB Output is correct
2 Correct 58 ms 124344 KB Output is correct
3 Correct 56 ms 124328 KB Output is correct
4 Correct 122 ms 124544 KB Output is correct
5 Correct 196 ms 124548 KB Output is correct
6 Correct 66 ms 124764 KB Output is correct
7 Correct 69 ms 124792 KB Output is correct
8 Correct 67 ms 124716 KB Output is correct
9 Correct 343 ms 135192 KB Output is correct
10 Runtime error 849 ms 666632 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -