AquaRio 的博客

AquaRio 的博客

题解 P3573 【[POI2014]RAJ-Rally】

posted on 2019-10-27 16:57:14 | under 题解 |

突然发现所有的题解都没有用multiset。

其它题解都是用权值线段树,或者是堆解决的问题。

但是权值线段树码量太大,堆跑得很慢。

为什么不了解一下又好写又跑得快的multiset呢?

// P3573.CPP

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

const int N = 5e5 + 5;
const int M = 1e6 + 5;

int n, m;
multiset<int> S;

struct edge {
    int v, nxt;
} e[M << 1];

int head[2][N], cnt, in[N], q[N], l, r;
int dis[2][N];

inline void add(int u, int v, int t) {
    e[++cnt].v = v;
    e[cnt].nxt = head[t][u];
    head[t][u] = cnt;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        in[v]++;
        add(u, v, 0);
        add(v, u, 1);
    }
    int pos = 0, dismin = n, tmp;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0)
            q[r++] = i;
    while (l < r) {
        int fr = q[l];
        l++;
        for (int i = head[0][fr]; i; i = e[i].nxt) {
            int to = e[i].v;
            in[to]--;
            if (!in[to])
                q[r++] = e[i].v;
        }
    }
    for (int k = 0; k <= n - 1; k++)
        for (int i = head[0][q[k]]; i; i = e[i].nxt)
            dis[0][e[i].v] = max(dis[0][e[i].v], dis[0][q[k]] + 1);
    for (int k = n - 1; k >= 0; k--)
        for (int i = head[1][q[k]]; i; i = e[i].nxt)
            dis[1][e[i].v] = max(dis[1][e[i].v], dis[1][q[k]] + 1);

    for (int i = 1; i <= n; i++)
        S.insert(dis[1][i]);
    for (int k = 0; k <= n - 1; k++) {
        S.erase(S.find(dis[1][q[k]]));
        for (int i = head[1][q[k]]; i; i = e[i].nxt)
            S.erase(S.find(dis[0][e[i].v] + dis[1][q[k]] + 1));
        tmp = *S.rbegin();
        if (tmp < dismin)
            dismin = tmp, pos = q[k];
        for (int i = head[0][q[k]]; i; i = e[i].nxt)
            S.insert(dis[0][q[k]] + dis[1][e[i].v] + 1);
        S.insert(dis[0][q[k]]);
    }
    cout << pos << " " << dismin << endl;
}