【题解】LOJ 2718 「NOI2018」归程

Problem

给定一张无向图,每条边有长度 $l$ ,海拔 $a$

每天给定 $p,v$
分别表示将在 $v$ 点出发,不能走海拔在 $p$ 之下的边

求能到达的节点距离节点 $1$ 最近的距离

Thought

法一

可持久化并查集

法二

kruskal 重构树 + 倍增

Code

法一

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
typedef pair<int, int> P;
const int N = 200010, M = 400010, INF = 1000000000;
struct edge {
    int t, n, l;
}e[M << 1];
struct EDGE {
    int x, y, l, h;
}E[M];
struct T {
    int l, r, fa, num, NUM;
} t[M * 30];
int cnt, rt[M];
int head[N], tot;
int qwe[M];
int n, m, q, k, s;
int dis[N], vis[N];
struct heap {
    P h[N << 1];
    int total;
    P get() { return h[1]; }
    void pop() {
        h[1] = (P){0, 0}; h[1] = h[total--];
        int now = 1, son;
        while (now * 2 <= total) {
            son = now * 2;
            if(son + 1 <= total && h[son + 1] < h[son]) ++ son;
            if(h[now] > h[son])
                swap(h[now], h[son]);
            else
                break;
            now = son;
        }
    }
    void push(int dis, int x) {
        h[++ total] = (P){ dis, x };
        int now = total;
        while (now / 2 && h[now] < h[now / 2]) {
            swap(h[now], h[now / 2]);
            now /= 2;
        }
        return;
    }
    void clear() {
        memset(h, 0, sizeof(h));
        total = 0;
    }
} h;

int read();
void work();
void addedge(int, int, int);
void dijkstra();
bool cmp(EDGE, EDGE);

void build(int &, int, int);
void insert(int &, int, int, int, int, int, int);  // rt,pos,l,r,fa,min_dis
int query(int rt, int pos, int l, int r);          // return fa
int getfa(int, int);                               // return grand
int query_node(int, int, int, int);
int main() {
    freopen("return.in", "r", stdin);
    freopen("return.out", "w", stdout);
    int TTT = read();
    while (TTT --)
        work();
    return 0;
}
void work() {
    memset(head, 0, sizeof(head));
    memset(qwe, 0, sizeof(qwe));
    memset(rt, 0, sizeof(rt));
    memset(t, 0, sizeof(t));
    h.clear();
    tot = 0;
    cnt = 0;
    n = read();
    m = read();
    for(int i = 1; i <= m; ++i) {
        E[i].x = read(); E[i].y = read();
        E[i].l = read(); E[i].h = read();
        addedge(E[i].x, E[i].y, E[i].l);
        addedge(E[i].y, E[i].x, E[i].l);
    }
    dijkstra();
    build(rt[0], 1, n);
    sort(E + 1, E + m + 1, cmp);
    for(int i = 1; i <= m; ++i) {
        qwe[m - i + 1] = E[i].h;
        rt[i] = rt[i - 1];
        int x = getfa(i, E[i].x);
        int y = getfa(i, E[i].y);
        if(x == y) continue;
        int nodex = query_node(rt[i], x, 1, n);
        int nodey = query_node(rt[i], y, 1, n);
        int num = min(t[nodex].num, t[nodey].num);
        int NUM = t[nodex].NUM + t[nodey].NUM;
        if(t[nodex].NUM >= t[nodey].NUM) {
            insert(rt[i], x, 1, n, x, num, NUM);
            insert(rt[i], y, 1, n, x, 0, 0);
        }
        else {
            insert(rt[i], x, 1, n, y, 0, 0);
            insert(rt[i], y, 1, n, y, num, NUM);
        }
    }
    q = read(); k = read(); s = read();
    int v, p, ans = 0;
    for(int i = 1; i <= q; ++i) {
        v = read(); p = read();
        v = (v + ((ll)k * ans - 1) % n) % n + 1;
        p = (p + ((ll)k * ans) % (s + 1)) % (s + 1);
        p = m - (upper_bound(qwe + 1, qwe + m + 1, p) - qwe) + 1;
        ans = getfa(p, v);
        ans = t[query_node(rt[p], ans, 1, n)].num;
        printf("%d\n", ans);
    }
}
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

void addedge(int x, int y, int l) {
    e[++ tot] = {y, head[x], l};
    head[x] = tot;
}
void dijkstra() {
    for(int i = 1; i <= n; ++i) {
        dis[i] = i == 1 ? 0 : INF;
        vis[i] = 0;
    }
    h.push(dis[1], 1);
    for(int i = 1; i <= n; ++i) {
        P x;
        do {
            x = h.get();
            h.pop();
        }while(vis[x.second]);
        vis[x.second] = 1;
        for(int j = head[x.second]; j; j = e[j].n) {
            int t = e[j].t;
            if(dis[t] > dis[x.second] + e[j].l) {
                dis[t] = dis[x.second] + e[j].l;
                h.push(dis[t], t);
            }
        }
    }
}
bool cmp(EDGE a, EDGE b) { return a.h > b.h; }

void build(int &rt, int l, int r) {
    t[++cnt] = t[rt];
    rt = cnt;
    if(l == r) {
        t[rt].fa = l;
        t[rt].num = dis[l];
        t[rt].NUM = 1;
        return;
    }
    build(t[rt].l, l, mid);
    build(t[rt].r, mid + 1, r);
}

void insert(int &rt, int pos, int l, int r, int fa, int num, int NUM) {
    t[++cnt] = t[rt];
    rt = cnt;
    if(l == r) {
        t[rt].fa = fa;
        t[rt].num = num;
        t[rt].NUM = NUM;
        return;
    }
    if(pos <= mid)
        insert(t[rt].l, pos, l, mid, fa, num, NUM);
    else
        insert(t[rt].r, pos, mid + 1, r, fa, num, NUM);
}
int query(int rt, int pos, int l, int r) {
    if(l == r)
        return t[rt].fa;
    if(pos <= mid)
        return query(t[rt].l, pos, l, mid);
    else
        return query(t[rt].r, pos, mid + 1, r);
}
int query_node(int rt, int pos, int l, int r) {
    if(l == r)
        return rt;
    if(pos <= mid)
        return query_node(t[rt].l, pos, l, mid);
    else
        return query_node(t[rt].r, pos, mid + 1, r);
}
int getfa(int b, int son) {
    int fa = query(rt[b], son, 1, n);
    while (son != fa) {
        son = fa;
        fa = query(rt[b], son, 1, n);
    }
    return fa;
}
Comments

添加新评论