Submission #378533

#	Time	Username	Problem	Language	Result	Execution time	Memory
378533		eric_xiao	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1231 ms	98492 KiB

plan

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define F first
#define S second
using namespace std;
vector<ll> G[100009],d[100009],tr[100009],td[100009];
ll dis[100009],DSU[100009],dep[100009];
ll A[500009],B[500009],C[500009];
vector<ll> np;
vector<ll> id;
const ll inf = 1000000000000000;
ll anc[19][100009],mx[19][100009];//mx is min
priority_queue<pll,vector<pll>,greater<pll> > pq;
const bool cmp(const ll &a,const ll &b)
{
    return C[a] > C[b];
}
ll Find(ll a)
{
    if(a == DSU[a]) return a;
    DSU[a] = Find(DSU[a]);
    return DSU[a];
}
void DFS(ll u,ll p,ll len)
{
    anc[0][u] = p;
    mx[0][u] = len;
    for(ll i = 0;i < tr[u].size();i++)
    {
        ll v = tr[u][i];
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        DFS(v,u,td[u][i]);
    }
}
ll LCA(ll a,ll b)
{
    if(dep[a] < dep[b]) swap(a,b);
    ll ret = inf;
    ll t = dep[a] - dep[b];
    for(ll i = 0;i < 19;i++)
    {
        if(1 & (t >> i))
        {
            ret = min(ret,mx[i][a]);
            a = anc[i][a];
        }
    }
    if(a == b) return ret;
    for(ll i = 18;i >= 0;i--)
    {
        if(anc[i][a] != anc[i][b])
        {
            ret = min({ret,mx[i][a],mx[i][b]});
            a = anc[i][a];
            b = anc[i][b];
        }
    }
    return min(ret,min(mx[0][a],mx[0][b]));
}
int main()
{
    ll T,N,M,i,j,k,a,b,c,Q;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for(i = 0;i < M;i++)
    {
        cin >> a >> b >> c;
        A[i] = a;
        B[i] = b;
        G[a].push_back(b);
        G[b].push_back(a);
        d[a].push_back(c);
        d[b].push_back(c);
        id.push_back(i);
    }
    for(i = 1;i <= N;i++)
    {
        dis[i] = inf;
    }
    cin >> k;
    for(i = 0;i < k;i++)
    {
        cin >> a;
        np.push_back(a);
        pq.push({0,a});
    }
    //cout << "OK" << endl;
    while(!pq.empty())
    {
        pll u = pq.top();
        pq.pop();
        if(dis[u.S] < inf) continue;
        dis[u.S] = u.F;
        for(i = 0;i < G[u.S].size();i++)
        {
            ll v = G[u.S][i];
            if(dis[v] < inf) continue;
            pq.push({dis[u.S]+d[u.S][i],v});
        }
    }
    for(i = 0;i < M;i++)
    {
        C[i] = min(dis[A[i]],dis[B[i]]);
    }
    sort(id.begin(),id.end(),cmp);
    for(i = 1;i <= N;i++) DSU[i] = i;
    for(i = 0;i < M;i++)
    {
        ll p = Find(A[id[i]]),q = Find(B[id[i]]);
        if(p == q) continue;
        DSU[p] = q;
        tr[A[id[i]]].push_back(B[id[i]]);
        tr[B[id[i]]].push_back(A[id[i]]);
        td[A[id[i]]].push_back(C[id[i]]);
        td[B[id[i]]].push_back(C[id[i]]);
    }
    dep[1] = 0;
    DFS(1,0,0);
    for(i = 1;i < 19;i++)
    {
        for(j = 1;j <= N;j++)
        {
            anc[i][j] = anc[i-1][anc[i-1][j]];
            mx[i][j] = min(mx[i-1][j],mx[i-1][anc[i-1][j]]);
        }
    }
    cin >> Q;
    //cout << "Q = " << Q << endl;
    for(i = 0;i < Q;i++)
    {
        cin >> a >> b;
        cout << LCA(a,b) << '\n';
    }
}

Compilation message (stderr)

plan.cpp: In function 'void DFS(long long int, long long int, long long int)':
plan.cpp:29:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(ll i = 0;i < tr[u].size();i++)
      |                  ~~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:97:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(i = 0;i < G[u.S].size();i++)
      |                   ~~^~~~~~~~~~~~~~~
plan.cpp:64:8: warning: unused variable 'T' [-Wunused-variable]
   64 |     ll T,N,M,i,j,k,a,b,c,Q;
      |        ^

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