Submission #515491

#	Time	Username	Problem	Language	Result	Execution time	Memory
515491		uHyHn	Evacuation plan (IZhO18_plan)	C++14	0 / 100	350 ms	63632 KiB

plan

#include<bits/stdc++.h>

//IBOW
#define Task "IZhO18_plan"
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define eb emplace_back
#define ll long long

using namespace std;

const int N = 2e5 + 10;
const int inf = 2e9 + 10;
const ll INF = 2e18 + 10;
const int MOD = 1e9 + 7;

/*

*/

int n, m, f[N], k, dist[N], q, par[N];
vector<pair<int, int>> g[N];
vector<pair<int, int>> edges;
map<int, int> mp[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

class Tree
{
public:
    int n, timer;
    vector<vector<int>> g, up, G;
    vector<int> tin, tout, dep;
    Tree()
    {
        n = 0;
    }
    Tree(int n)
    {
        this->n = n;
        g.assign(n + 7, vector<int>());
        up.assign(n + 7, vector<int>(21));
        G.assign(n + 7, vector<int>(21, inf));
        tin.assign(n + 7, 0);
        tout.assign(n + 7, 0);
        dep.assign(n + 7, 0);
        timer = 0;
    }
    void addedges(int u, int v)
    {
        g[u].pb(v);
        g[v].pb(u);
    }
    void dfs(int u, int p = 0)
    {
        tin[u] = ++timer;
        up[u][0] = p;
//        cout << dist[p] << '\n';
        G[u][0] = min({G[u][0], dist[p]});
        for (int d = 1; d < 21; ++d)
        {
            up[u][d] = up[up[u][d - 1]][d - 1];
            G[u][d] = min({G[u][d], G[u][d - 1], G[up[u][d - 1]][d - 1]});
        }
//        cout << u << '\n';
        for (int e : g[u])
        {
            if (e == p) continue;
            dep[e] = dep[u] + 1;
            dfs(e, u);
        }
        tout[u] = ++timer;
    }
    bool acestor(int u, int v)
    {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }
    int lca(int u, int v)
    {
        if (acestor(u, v)) return u;
        if (acestor(v, u)) return v;
        for (int i = 20; i >= 0; --i)
        {
            if (!acestor(up[u][i], v))
                u = up[u][i];
        }
        return up[u][0];
    }
    int getmin(int u, int v)
    {
        int d = dep[u] - dep[v];
        int ans = min(dist[u], dist[v]);
        for (int i = 20; i >= 0; --i) if (d & (1 << i))
        {
            ans = min(ans, G[u][i]);
            u = up[u][i];
        }
        return ans;
    }
    int query(int u, int v)
    {
        int LCA = lca(u, v);
//        cout << u << " " << v << " " << LCA << '\n';
        return min(getmin(u, LCA), getmin(v, LCA));
    }
};

int Find(int u)
{
    return (par[u] == u ? u : par[u] = Find(par[u]));
}


bool cmp(pair<int, int> a, pair<int, int> b)
{
    return dist[a.F] > dist[b.F];
}
void Deogiaibalamcho()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, c;
        cin >> u >> v >> c;
//        g[u].pb({v, c});
//        g[v].pb({u, c});
        if (u > v) swap(u, v);
        edges.pb({u, v});
        mp[u][v] = max(mp[u][v], c);
    }
    sort(all(edges));
    edges.erase(unique(all(edges)), edges.end());
    for (pair<int, int> e : edges)
    {
//        cout <<
        g[e.F].pb({e.S, mp[e.F][e.S]});
        g[e.S].pb({e.F, mp[e.F][e.S]});
    }
    for (int i = 1; i <= n; ++i) par[i] = i;
//    for (int i = 1; i <= n; ++i) sort(all(edges[i]));
    fill(&dist[0], &dist[0] + N, inf);
    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        cin >> f[i];
        pq.push({0, f[i]});
        dist[f[i]] = 0;
    }
    vector<pair<int, int>> snt;
    while (!pq.empty())
    {
        pair<int, int> u = pq.top();
        pq.pop();
        if (u.F != dist[u.S]) continue;
        for (pair<int, int> e : g[u.S])
        {
            if (dist[e.F] > u.F + e.S)
            {
                dist[e.F] = u.F + e.S;
                pq.push({dist[e.F], e.F});
            }
        }
    }
//    for (int i = 1; i <= n; ++i) cout << dist[i] << '\n';
    for (int i = 1; i <= n; ++i) snt.pb({dist[i], i});
    sort(all(snt), greater<pair<int, int>>());
    for (int i = 1; i <= n; ++i) sort(all(g[i]), cmp);
    Tree res;
    res = Tree(n);
    for (pair<int, int> u : snt)
    {
//        cout << u.F << ' ' << u.S << '\n';
        for (pair<int, int> e : g[u.S]) if (Find(e.F) != Find(u.S))
        {
            if (dist[e.F] < dist[u.S] || (dist[e.F] == dist[u.S] && e.F < u.S))
            {
                par[Find(e.F)] = Find(u.S);
                res.addedges(u.S, e.F);
            }
        }
    }
    res.dfs(Find(1));
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        cout << res.query(u, v) << '\n';
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen(Task".inp", "r"))
    {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t--) Deogiaibalamcho();
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int32_t main()':
plan.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(Task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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