https://atcoder.jp/contests/abc305/tasks_print

E - Art Gallery on Graph

冷知识：md 这题赛时没做出来 /cy

刚看到题：这是什么题啊，\(K, h\) 都 \(1e5\) 能做吗 /fn

确实能做。

考虑类似 SPFA 的操作。

设 \(a_x\) 表示 \(x\) 还可以对距离最多为 \(a_x\) 的点产生贡献，然后就直接 BFS 即可，用一个队列维护。

那么问题来了，它 WA 了。

发现这个过程类似于最短路，所以这不能单纯的用 queue 做。

类似 Dijkstra，要用大的更新小的，可能就有一个特别大的点去更新了队内的点，所以要用 priority_queue 维护，赛时太单纯了，没有想到。/ll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int n, m, k;
int cnt, head[200005], rem[200005], ans[200005];
struct edge {
	int to, nxt;
} ed[400005];
inline void add_edge (int u, int v) {
	cnt ++;
	ed[cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}
priority_queue < pair < int, int > > q;
signed main () {
	read (n), read (m), read (k);
	while (!q.empty ()) q.pop ();
	for (int i = 1;i <= m; ++ i) {
		int u, v;
		read (u), read (v);
		add_edge (u, v);
		add_edge (v, u);
	}
	for (int i = 1;i <= n; ++ i) rem[i] = -1;
	for (int i = 1;i <= k; ++ i) {
		int x, y;
		read (x), read (y);
		rem[x] = y;
		q.push (make_pair (y, x));
	}
	while (!q.empty ()) {
		int u = q.top ().second, w = q.top ().first;
		q.pop ();
		ans[u] = 1;
		if (rem[u] != w) continue;
		for (int i = head[u]; i ; i = ed[i].nxt) {
			int v = ed[i].to;
			if (rem[v] < rem[u] - 1) {
				rem[v] = rem[u] - 1;
				q.push (make_pair (rem[v], v));
			}
		} 
	}
	int qwq = 0;
	for (int i = 1;i <= n; ++ i) {
		qwq += ans[i];
	}
	printf ("%d\n", qwq);
	for (int i = 1;i <= n; ++ i) {
		if (ans[i]) printf ("%d ", i);
	}
	printf ("\n");
	return 0;
}
// Always keep it simple and stupid

F - Dungeon Explore

差点没做出来。

如果是一个图，我们会发现这很烦人。

如果是一棵树，那就会很好做。

因为一个图总是可以删掉一些边当成一棵树做，所以我们考虑 \(m = n - 1\) 的情况。

那么我们就以 \(1\) 为根开始遍历，类似于回溯那种，遍历完 \(u\) 的子树就回溯。

每个节点都会被遍历一次，每个节点都会被回溯一次。

所以操作次数最多为 \(2n\)。

就做完了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int mp[105], n, m, no;
inline void dfs (int u, int fa) {
	if (no) cout << u << endl;
	no = 1;
	mp[u] = 1;
	if (u == n) {
		string s;
		cin >> s;
		exit (0);
	}
	vector < int > st; st.clear ();
	int x;
	read (x);
	for (int i = 1;i <= x; ++ i) {
		int v; read (v);
		st.push_back (v);
	}
	for (int i = 1;i <= x; ++ i) {
		int v = st[i - 1];
		if (!mp[v] && v != fa) dfs (v, u); 
	}
	cout << fa << endl;
	read (x);
	for (int i = 1;i <= x; ++ i) {
		int v; read (v);
	}
}
signed main () {
	read (n), read (m);
	dfs (1, 0);
	return 0;
}
// Always keep it simple and stupid