Submission #1093981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093981		HNa_seawjing	Evacuation plan (IZhO18_plan)	C++17	0 / 100	143 ms	81464 KiB

plan

#include <bits/stdc++.h>
//code
#define fl(i,x,y,z) for(int i=x;i<=y;i=i+z)
#define fn(i,x,y,z) for(int i=x;i>=y;i=i-z)
#define rep(i,x,y) for(int i=x;i<y;i=i+1)
#define all(v) v.begin(),v.end()
#define pb emplace_back
#define tle cout<<"tle"<<endl
#define edl cout<<"\n"
#define el "\n"
#define getbit(x,i) ((x>>i)&1)
#define bitcnt __builtin_popcount
//ham
//#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ld long double
using namespace std;

const int N = int(5e5) + 7;
const int inf = 1e9 + 1;
typedef pair<ll, ll> pii;

int n, m, k, d[N], p, u, v, w;
vector<pii> e[N];
struct TEdges {
    int u, v, w;
    TEdges() {u = v = w = 0;}
    TEdges(int u, int v, int w): u(u), v(v), w(w) {}
    bool operator < (const TEdges& x)const& {
        return w > x.w;
    }
};
vector<TEdges> edges;
priority_queue<pii, vector<pii>, greater<pii>> q;

int lab[N],sz[N];
int findset(int u)
{
    if (lab[u]==u) return u;
    return lab[u]=findset(lab[u]);
}
bool joinset(int u,int v)
{
    u=findset(u),v=findset(v);
    if (u==v) return false;
    if (sz[u]<sz[v]) swap(u,v);
    lab[v]=u;
    sz[u]+=sz[v];
    return true;
}

const int logN = 20;
int f[N][logN + 1], g[N][logN + 1], h[N];
void DFS(int u)
{
    for (auto it: e[u])
    {
        int v=it.fi,c=it.se;
        if (v==f[u][0]) continue;
        h[v]=h[u]+1;
        f[v][0]=u;
        g[v][0]=c;
        fl(i,1,18,1)
        {
            f[v][i]=f[f[v][i-1]][i-1];
            g[v][i]=min(g[v][i-1],g[f[v][i-1]][i-1]);
        }
        DFS(v);
    }
}
int lca(int u, int v) {
    if (h[u]<h[v]) swap(u,v);
    int res=inf;
    int k=h[u]-h[v];
    fn(i,17,0,1)
        if (getbit(k,i))
        {
            res=min(res,g[u][i]);
            u=f[u][i];
        }
    if (u==v) return res;
    fn(i,17,0,1)
        if (f[u][i]!=f[v][i])
        {
            res=min(res,g[u][i]);
            res=min(res,g[v][i]);
            u=f[u][i],v=f[v][i];
        }
    res=min(res,g[u][0]);
    res=min(res,g[v][0]);
    return res;
}
void inp()
{
    cin >> n >> m>>k>>p;
    fl(i,1,m,1)
    {
        int u,v,w; cin>>u>>v>>w;
        e[u].pb(v,w);
        e[v].pb(u,w);
        edges.pb(u,v,w);
    }
    fill_n(&g[0][0], N * (logN + 1), inf);
    fl(i,1,n,1)
    {
        lab[i]=i;
        sz[i]=1;
    }
    fill(d, d + n + 1, inf);
    fl(i,1,k,1)
    {
        cin >> u;
        d[u] = 0, q.emplace(d[u], u);
    }
}
void sol()
{
    pii top;
    while(q.size()) {
        top = q.top(); q.pop();
        if(top.fi != d[top.se]) continue;
        for(auto& v: e[top.se]) {
            if(top.fi + v.se < d[v.fi]) {
                d[v.fi] = top.fi + v.se;
                q.emplace(d[v.fi], v.fi);
            }
        }
    }
    for(auto& it: edges) it.w = min(d[it.u], d[it.v]);
    sort(edges.begin(), edges.end());
    fl(i,1,n,1) e[i].clear();
    for(auto &it: edges) {
        if(joinset(it.u, it.v)) {
            e[it.u].pb(it.v, it.w);
            e[it.v].pb(it.u, it.w);
        }
    }
    DFS(1);
    while(p --) {
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}
signed main()
{
    #define name "walk"
    if (fopen(name".inp", "r"))
    {
        freopen(name".inp", "r", stdin);
        freopen(name". Out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inp();
    sol();
    return 0;
}

Compilation message (stderr)

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

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