求助,请勿无意义回复
QAQ
我比较菜不会kruskal重构树于是写了可持久化并查集
UOJ:http://uoj.ac/submission/411661
Luogu:https://www.luogu.com.cn/record/34916025
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
const int N = 2e5 + 5;
const int M = 4e5 + 5;
const int Q = 4e5 + 5;
int n, m, q, K, S;
struct edge {
int to, length, height;
edge(int v, int w, int h) {
to = v, length = w, height = h;
}
};
vector<edge> G[N];
int edge_u[M], edge_v[M];
vector<pair<int, int> > height;
/*height & index*/
template<class T>
struct PerArray {
int lc[N << 5], rc[N << 5];
int root[M];
T val[N << 5];
int timer, total;
#define mid ((l + r) >> 1)
int __upd_val(int p, T v, int l, int r, int pre) {
int x = ++total;
lc[x] = lc[pre], rc[x] = rc[pre];
if (l == r) return val[x] = v, x;
if (p <= mid) lc[x] = __upd_val(p, v, l, mid, lc[pre]);
else rc[x] = __upd_val(p, v, mid + 1, r, rc[pre]);
return x;
}
T __get_val(int x, int p, int l, int r) {
if (l == r) return val[x];
if (p <= mid) return __get_val(lc[x], p, l, mid);
else return __get_val(rc[x], p, mid + 1, r);
}
int __build_tree(int l, int r, T* d) {
int x = ++total;
if (l == r) return val[x] = d[l], x;
lc[x] = __build_tree(l, mid, d);
rc[x] = __build_tree(mid + 1, r, d);
return x;
}
#undef mid
void update(int p, T v) {
timer++;
root[timer] = __upd_val(p, v, 0, n, root[timer - 1]);
}
T at(int t, int p) {
return __get_val(root[t], p, 0, n);
}
void copy() {
root[++timer] = root[timer - 1];
}
void init(T* d) {
root[0] = __build_tree(0, n, d);
}
void reset() {
timer = total = 0;
}
};
struct PERSISTENT_DSU{
PerArray<int> p_fa;
PerArray<long long> p_dis;
int fa[N], size[N];
long long dis[N];
int find(int u) {
return u == fa[u] ? u : find(fa[u]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (u == v) return p_fa.copy(), p_dis.copy();
if (size[u] > size[v]) swap(u, v);
fa[u] = v, size[v] += size[u], dis[v] = min(dis[v], dis[u]);
p_fa.update(u, v), p_dis.update(v, dis[v]);
}
void init(long long* d) {
p_fa.reset(), p_dis.reset();
for (register int i = 1; i <= n; i++) fa[i] = i;
for (register int i = 1; i <= n; i++) size[i] = 1;
for (register int i = 1; i <= n; i++) dis[i] = d[i];
p_fa.init(fa), p_dis.init(dis);
}
} pdsu;
struct SINGLE_SOURCE_SHORTEST_PATH{
long long dis[N];
bool book[N];
struct heapNode {
int pos;
long long dis;
heapNode(int p, long long d) : pos(p), dis(d) { }
bool operator < (const heapNode& t) const {
return dis > t.dis;
}
};
priority_queue<heapNode> pq;
void Dijkstra() {
memset(dis, 0x3f, sizeof dis);
memset(book, 0, sizeof book);
while (!pq.empty()) pq.pop();
pq.push(heapNode(1, dis[1] = 0));
while (!pq.empty()) {
heapNode x = pq.top();
pq.pop();
if (book[x.pos]) continue;
book[x.pos] = true;
for (vector<edge>::iterator it = G[x.pos].begin(); it != G[x.pos].end(); it++) {
int to = it->to, len = it->length;
if (dis[to] > len + x.dis) {
dis[to] = len + x.dis;
pq.push(heapNode(to, dis[to]));
}
}
}
}
} sssp;
long long query(int v, int p) {
int time = height.end()
- upper_bound(height.begin(), height.end(), make_pair(p, 0x3f3f3f3f));
int pos = v;
for (register int f; ; ) {
f = pdsu.p_fa.at(time, pos);
if (f == pos) break;
pos = f;
}
return pdsu.p_dis.at(time, pos);
}
void solve() {
io::gi(n), io::gi(m);
for (register int i = 1; i <= n; i++)
G[i].clear();
height.clear(), height.resize(m);
for (register int i = 1; i <= m; i++) {
int u, v, w;
io::gi(u), io::gi(v), io::gi(w), io::gi(height[i - 1].first);
G[u].push_back(edge(v, w, height[i - 1].first));
G[v].push_back(edge(u, w, height[i - 1].first));
height[i - 1].second = i;
edge_u[i] = u, edge_v[i] = v;
}
sssp.Dijkstra();
pdsu.init(sssp.dis);
sort(height.begin(), height.end());
for (register int i = m - 1; ~i; i--)
pdsu.connect(edge_u[height[i].second], edge_v[height[i].second]);
io::gi(q), io::gi(K), io::gi(S);
long long last = 0;
while (q--) {
int v, p;
io::gi(v), io::gi(p);
v = (v + K * last - 1) % n + 1;
p = (p + K * last) % (S + 1);
last = query(v, p);
io::print(last), io::pc('\n');
}
}
signed main() {
int test_case;
io::gi(test_case);
while (test_case--)
solve();
return 0;
}