제출 #572218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572218		Doanxem99	Evacuation plan (IZhO18_plan)	C++14	100 / 100	665 ms	165188 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ar array< int , 2>
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
template<typename T1, typename T2> bool minN(T1 &a, T2 b) {if (a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxX(T1 &a, T2 b) {if (a < b) a = b; else return 0; return 1;}
const int MAX = 1e6 + 1000, INFL = 1e9 + 7, LOG = 18;
int  n, m, x, y, z, k, f[LOG + 1][MAX], minDanger[LOG + 1][MAX], high[MAX], q;
bool NSS[MAX], par[MAX];
ar d[MAX], dd[MAX];
vector < ar > A[MAX];
vector < int > B[MAX];
struct DSU
{
    vector < long long > ff;
    void Init(long long _n) {ff.resize(_n + 100, -1);}

    long long Root(long long x) {return (ff[x] <= -1 ? x : ff[x] = Root(ff[x]));}

    bool Join(long long x, long long y)
    {
        x = Root(x); y = Root(y);
        if (x == y) return false;
        if (ff[x] > ff[y]) swap(x, y);
        ff[x] += ff[y]; ff[y] = x;
        return true;
    }

    bool Check(long long x, long long y) {return Root(x) == Root(y);}
};
DSU dsu;
void BFS()
{
    queue< ar > QU;
    for (int i = 1; i <= n; i++) if (NSS[i]) QU.push({0, i}), d[i][0] = 0;
    while (!QU.empty())
    {
        ar x = QU.front();
        QU.pop();
        //if (d[x[1]][0] != x[0]) continue;
        for (ar y : A[x[1]])
        {
            if (d[y[0]][0] > x[0] + y[1])
            {
                d[y[0]][0] = x[0] + y[1];
                QU.push({d[y[0]][0], y[0]});
            }
        }
    }
}
bool Compare(ar x, ar y)
{
    return d[x[0]] > d[y[0]];
}
void MakeTree()
{
    for (int i = 1; i <= n; i++)
    {
        dd[i] = d[i];
    }
    sort(dd + 1, dd + 1 + n, greater< ar >());
    for (int i = 1; i <= n; i++)
    {
        ar x = dd[i];
        par[x[1]] = 1;
        sort(A[x[1]].begin(), A[x[1]].end(), Compare);
        for (ar y : A[x[1]])
        {
            if (par[y[0]] && dsu.Join(x[1], y[0]))
            {
                B[x[1]].push_back(y[0]);
                B[y[0]].push_back(x[1]);
            }
        }
    }
}
void DFS(int x, int p)
{
    for (int y : B[x])
    {
        if (p != y)
        {
            f[0][y] = x;
            minDanger[0][y] = min(d[y][0], d[x][0]);
            //cout << y << " " << minDanger[0][y] << '\n' ;
            high[y] = high[x] + 1;
            DFS(y, x);
        }
    }
}
void Prepare()
{
    high[0] = -1;
    DFS(1, 0);
    for (int k = 1; k <= LOG; k++)
    {
        for (int x = 1; x <= n; x++)
        {
        f[k][x] = f[k - 1][f[k - 1][x]];
        minDanger[k][x] = min(minDanger[k - 1][x], minDanger[k - 1][f[k - 1][x]]);
        }
    }
}
int LCA(int x, int y)
{
    if (high[x] < high[y]) return LCA(y, x);
    int ans = INFL;
    for (int k = LOG; k >= 0; k--)
    {
        if (high[f[k][x]] >= high[y])
            minN(ans, minDanger[k][x]), x = f[k][x];
    }
    //cout << ans << '\n' ;
    if (x == y) return ans;
    for (int k = LOG; k >= 0; k--)
    {
        if (f[k][x] != f[k][y])
        {
            minN(ans, minDanger[k][x]);
            minN(ans, minDanger[k][y]);
            x = f[k][x];
            y = f[k][y];
        }
    }
    while (x != y)
    {
        minN(ans, minDanger[0][x]);
        minN(ans, minDanger[0][y]);
        x = f[0][x];
        y = f[0][y];
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(minDanger, 0x3f, sizeof minDanger);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    dsu.Init(n);
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        A[x].push_back({y, z});
        A[y].push_back({x, z});
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> x;
        NSS[x] = 1;
    }
    for (int i = 1; i <= n; i++) d[i][1] = i;
    BFS();
    MakeTree();
    Prepare();
    //for (int i = 1; i <= n; i++) for (int j : B[i]) if (i < j) cout << i << " " << j << '\n' ;
    //cout << '\n' ;
    //for (int i = 1 ;i <= n; i++) cout << d[i][0] << " " << d[i][1] << '\n' ;
    cin >> q;

    for (int i = 1; i <= q; i++)
    {
        cin >> x >> y;
        //cout << minDanger[0][x] << " " << minDanger[0][y] << '\n' ;
        cout << LCA(x, y) << '\n' ;
    }
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46