Submission #1211681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211681		adhityamv	Evacuation plan (IZhO18_plan)	C++20	100 / 100	526 ms	103048 KiB

plan

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define ll long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
//const int INF=1000000000000000000;
const int INF=1e9;
const int N=1000000;
const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << "," << p.se << " ";
}
int pow2[N];
int dist[N];
struct krt{
    int n;
    vector<int> link;
    vector<int> q;
    vector<int> parent;
    vector<vector<int>> children;
    krt(int nn){
        n=nn;
        for(int i=0;i<n;i++){
            link.push_back(i);
            q.push_back(dist[i]);
            children.push_back({});
            parent.push_back(-1);
        }
    }
    int findroot(int x){
        if(link[x]==x) return x;
        return (link[x]=findroot(link[x]));
    }
    bool unite(int x,int y,int qv){
        x=findroot(x);
        y=findroot(y);
        if(x==y) return false;
        int nv=link.size();
        link.push_back(nv);
        parent.push_back(-1);
        link[x]=link[y]=parent[x]=parent[y]=nv;
        q.push_back(qv);
        children.push_back({});
        children[nv].push_back(x);
        children[nv].push_back(y);
        return true;
    }
    vector<int> et;
    vector<vector<int>> sparsetable;
    vector<int> pos;
    void dfs(int u){
        pos[u]=(et.size());
        et.push_back(u);
        for(int v:children[u]){
            dfs(v);
            et.push_back(u);
        }
    }
    void init(){
        for(int i=0;i<2*n-1;i++) pos.push_back(-1);
        assert(link.size()==2*n-1);
        dfs(2*n-2);
        int m=et.size();
        for(int i=0;i<m;i++){
            sparsetable.push_back({});
            sparsetable[i].push_back(et[i]);
        }
        for(int j=0;j<ln-1;j++){
            for(int i=0;i<m;i++){
                if(i+(1<<j)>=m) sparsetable[i].push_back(sparsetable[i][j]);
                else sparsetable[i].push_back(max(sparsetable[i][j],sparsetable[i+(1<<j)][j]));
            }
        }
    }
    int lca(int u,int v){
        int i=pos[u];
        int j=pos[v];
        if(i>j) swap(i,j);
        int ind=pow2[j-i+1];
        return q[max(sparsetable[i][ind],sparsetable[j-(1<<ind)+1][ind])];
    }
};
void solve(){
    int n,m;
    cin >> n >> m;
    vector<pii> edges[n];
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u--,v--;
        edges[u].push_back(mp(v,w));
        edges[v].push_back(mp(u,w));
    }
    for(int i=0;i<n;i++) dist[i]=INF;
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    int k;
    cin >> k;
    vector<int> npp;
    for(int i=0;i<k;i++){
        int u;
        cin >> u;
        u--;
        npp.push_back(u);
    }
    for(int u:npp){
        dist[u]=0;
        pq.push(mp(0,u));
    }
    while(!pq.empty()){
        int u=pq.top().se;
        if(dist[u]!=pq.top().fi){
            pq.pop();
            continue;
        }
        pq.pop();
        for(auto [v,w]:edges[u]){
            if(dist[v]>w+dist[u]){
                dist[v]=w+dist[u];
                pq.push(mp(dist[v],v));
            }
        }
    }
    vector<pii> vert;
    for(int i=0;i<n;i++) vert.push_back(mp(-dist[i],i));
    sort(vert.begin(),vert.end());
    bool visited[n];
    for(int i=0;i<n;i++) visited[i]=false;
    krt dsu(n);
    //for(int i=0;i<n;i++) cout << i << " " << i << " " << dist[i] << "\n";
    for(auto [d,u]:vert){
        for(auto [v,w]:edges[u]){
            if(visited[v]){
                //cout << u << " " << v << " " << -d << "\n";
                dsu.unite(u,v,-d);
            }
        }
        visited[u]=true;
    }
    dsu.init();
    int q;
    cin >> q;
    while(q--){
        int u,v;
        cin >> u >> v;
        u--,v--;
        //cout << u << " " << v << "\n";
        cout << dsu.lca(u,v) << "\n";
    }
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    pow2[1]=0;
    for(int i=2;i<N;i++){
        if(i==(1<<(pow2[i-1]+1))) pow2[i]=pow2[i-1]+1;
        else pow2[i]=pow2[i-1];
    }
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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