Submission #748796

#	Time	Username	Problem	Language	Result	Execution time	Memory
748796		amogususus	Evacuation plan (IZhO18_plan)	C++17	23 / 100	610 ms	91548 KiB

plan

#pragma GCC optimize("Ofast,unroll-loops,inline")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
using namespace std;
const int maxN=1e5+2;
ll n,m,k,q,dist[maxN],lab[maxN];
vector<pll> adj[maxN];
bool cs(pll x,pll y){return x.second<y.second;}
ll fset(ll x){return lab[x]<0?x:lab[x]=fset(lab[x]);}
void uset(ll x,ll y){
    if((x=fset(x))!=(y=fset(y))){
        if(lab[x]>lab[y])swap(x,y);
        lab[x]+=lab[y];
        lab[y]=x;
    }
}

priority_queue<pll,vector<pll>,greater<pll>> pq;
void dijkstra(){
    while (!pq.empty()) {
        ll u = pq.top().second;pq.pop();
        for (auto x : adj[u]) {
            ll v = x.first,w = x.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
vector<pair<ll,pll>> edg;
vector<ll> g[maxN];
ll d[maxN],tin[maxN],tout[maxN],up[maxN][20],mx[maxN][20],timer=0;
void dfs(ll u=1,ll p=1){
    tin[u] = ++timer;
    up[u][0] = p;
    mx[u][0] = dist[u];
    for (int i = 1; i < 20; ++i)
        up[u][i] = up[up[u][i-1]][i-1],
        mx[u][i] = min(mx[u][i-1],mx[up[u][i-1]][i-1]);
    for(auto v:g[u])
        if(v!=p)dfs(v,u);
    tout[u] = ++timer;
}
bool is_ancestor(int u, int v){return tin[u] <= tin[v] && tout[u] >= tout[v];}
int lca(int u, int v){
    if (is_ancestor(u, v))return u;
    if (is_ancestor(v, u))return v;
    for (int i = 19; i >= 0; --i)
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    return up[u][0];
}
ll res[maxN];
ll getmax(ll u,ll v){
    ll r=1e18;
    for (int i = 19; i >= 0; --i)
        if (!is_ancestor(up[u][i], v))
            r=min(r,mx[u][i]),
            u = up[u][i];
    return min(r,mx[u][0]);
}
void Enter(){
    memset(lab,-1,sizeof lab);
    cin>>n>>m;
    for(int i=1;i<=n;i++)dist[i]=1e15;
    for(int i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        edg.pb({-69,{u,v}});
    }
    for(int i=1;i<=n;i++)sort(all(adj[i]),cs);
    cin>>k;
    for(int i=1;i<=k;i++){
        ll u;
        cin>>u;
        dist[u]=0;
        pq.push({0,u});
    }
    ///
    dijkstra();
    for(int i=0;i<edg.size();i++)edg[i].first=min(dist[edg[i].second.first],dist[edg[i].second.second]);
    sort(all(edg),greater<pair<ll,pll>>());
    for(auto x:edg){
        ll u=x.second.first,v=x.second.second;
        if(fset(u)!=fset(v))uset(u,v),g[u].pb(v),g[v].pb(u);
    }
    dfs();
    cin>>q;
    for(int i=1;i<=q;i++){
        ll u,v;
        cin>>u>>v;
        cout<<min(getmax(u,lca(u,v)),getmax(v,lca(u,v)))<<endl;
    }
}
//amogus
signed main(){
    open("EVACUATION");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    ll t=1;
    //cin>>t;
    while(t--)
    Enter();
}

Compilation message (stderr)

plan.cpp: In function 'void Enter()':
plan.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<edg.size();i++)edg[i].first=min(dist[edg[i].second.first],dist[edg[i].second.second]);
      |                 ~^~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:10:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:109:5: note: in expansion of macro 'open'
  109 |     open("EVACUATION");
      |     ^~~~
plan.cpp:10:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:109:5: note: in expansion of macro 'open'
  109 |     open("EVACUATION");
      |     ^~~~

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