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
标签:__,AtCoder,gnu,int,题解,tree,305,pbds,include
From: https://www.cnblogs.com/RB16B/p/17473669.html