Submission #552224

#	Time	Username	Problem	Language	Result	Execution time	Memory
552224		LucaDantas	Jail (JOI22_jail)	C++17	72 / 100	5119 ms	838288 KiB

jail

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 120010;

struct Top {
	vector<int> g[maxn];
	int ingrau[maxn];
	queue<int> q;
	void add_edge(int a, int b) {
		if(a == b) return;
		// 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], depth[maxn], comeca[maxn], termina[maxn]; // salvo o indice do cara que comeca e termina em mim caso exista
int s[maxn], t[maxn];
bool mark[maxn];
vector<int> g[maxn];

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

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

void go(int id) {
	// printf("go id %d\n", id);
	int a = s[id], b = t[id];
	if(termina[a]) // alguem termina em a (eu sei que eu comeco em a)
		top.add_edge(id, termina[a]); // eu tenho q sair antes do cara que termina aqui
	if(comeca[b]) // algue comeca em b (eu termino lá), então tenho q sair depois do cara ter terminado
		top.add_edge(comeca[b], id);
	for(; a != b;) {
		if(depth[a] < depth[b])
			swap(a, b);
		a = p[a];
		// printf("%d\n", a);
		if(termina[a])
			top.add_edge(id, termina[a]);
		if(comeca[a])
			top.add_edge(comeca[a], id);
	}
	// puts("");
}

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);
		int m; scanf("%d", &m);
		for(int i = 1; i <= m; i++)
			scanf("%d %d", s+i, t+i), comeca[s[i]] = i, termina[t[i]] = i;
		for(int i = 1; i <= m; i++)
			go(i);
		puts(top.dag(n) ? "Yes" : "No");
	}
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
jail.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
jail.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
      |    ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:84:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   int m; scanf("%d", &m);
      |          ~~~~~^~~~~~~~~~
jail.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |    scanf("%d %d", s+i, t+i), comeca[s[i]] = i, termina[t[i]] = i;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23