Submission #1098131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098131		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1125 ms	126024 KiB

plan

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define fx cout << fixed << setprecision(6);
#define md (tl+tr)/2
#define TL v+v, tl,md
#define TR v+v+1, md+1,tr
#define Tl t[v].l, tl,md
#define Tr t[v].r, md+1,tr
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define all(x) (x).begin(), (x).end()
#define int ll
#define cnk(n,k) mod(mod(f[(n)]*binpow(f[(n)-(k)],M-2))*binpow(f[(k)],M-2))
#define cnkf(n,k) mod(mod(f[(n)]*inv[(n)-(k)])*inv[(k)])

using namespace std;

typedef complex<double> cd;

struct mine{int l;int r;int i;};
struct edge{int u;int v;int w;};
struct tree{int l;int r;int val;};

auto cmp = [](mine a, mine b) { return a.i<b.i; };

mt19937 RR((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 
int random(int l, int r){
  return uniform_int_distribution<int>(l, r)(RR);
}

int M=998244353;

int mod1(int a,int b=M) {
    if (a<0)
        a=b+a%b;
    return a % b;
}

int binpow(int a,int n,int m=M) {
    a=mod1(a,m);
    if (!n)
        return 1;
    if (n&1)
        return (a * binpow(a,n-1))%m;
    int x = binpow(a,n>>1);
    return (x*x)%m; 
}

const ll INF=1e18+7;
const int N=5e5+7;

int n,m,qs,k,npp[N],d[N],ans[N],p[N],sz[N],s[N],t[N];
vector <pair <int,int>> g[N];
vector <mine> f[2][N];
bool u[N];
pair <int,int> a[N];

int find(int v) {
    if (p[v]==v)
        return v;
    return p[v]=find(p[v]);
}

void unite(int u,int v) {
    u=find(u), v=find(v);
    if (u==v)
        return;
    if (sz[u]>sz[v])
        swap(u,v);
    p[v]=u;
    sz[u]+=sz[v];
}

bool check(int i) {
    return u[s[i]] and u[t[i]] and find(s[i])==find(t[i]);
}

void solve() {
    cin >> n >> m;
    while (m--) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].eb(v,w);
        g[v].eb(u,w);
    }
    for (int i=1;i<=n;i++)
        d[i]=INF;
    cin >> k;
    set <pair <int,int>> q;
    for (int i=1;i<=k;i++) {
        cin >> npp[i];
        d[npp[i]]=0;
        q.insert({0,npp[i]});
    }
    while (!q.empty()) {
        int v=q.begin()->S;
        q.erase(q.begin());
        for (auto now : g[v]) {
            int to=now.F, val=now.S;
            if (d[to]>d[v]+val) {
                q.erase({d[to],to});
                d[to]=d[v]+val;
                q.insert({d[to],to});
            }
        }
    }
    for (int i=1;i<=n;i++) {
        a[i]={d[i],i};
        // cout << d[i] << ' ';
    }
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    cin >> qs;
    for (int i=1;i<=qs;i++) {
        cin >> s[i] >> t[i];
        int mid=(n+1)/2;
        f[0][mid].pb({0,n+1,i});
    }
    for (int i=0;i<20;i++) {
        for (int j=1;j<=n;j++) {
            p[j]=j;
            sz[j]=1;
            u[j]=false;
        }
        for (int j=1;j<=n;j++) {
            int v=a[j].S;
            u[v]=true;
            for (auto now : g[v]) {
                int to=now.F;
                if (u[to])
                    unite(v,to);
            }
            for (auto now : f[i%2][j]) {
                int l=now.l,r=now.r;
                if (check(now.i))
                    r=j;
                else
                    l=j;
                int mid=(l+r)/2;
                if (l+1<r)
                    f[(i+1)%2][mid].pb({l,r,now.i});
                else
                    ans[now.i]=d[a[r].S];
            }
            f[i%2][j].clear();
        }
    }
    for (int i=1;i<=qs;i++) {
        // cout << s[i] << ' ' << t[i] << ' ';
        cout << ans[i] << '\n';
    }
}   

signed main() {
    /*
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    */
    // fx
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
            count++;
        }
    }
    return 0;
}

// ctrl + shift + p make stress isis__Good isis__Generator

// g++ -std=c++17 (path) -o run
// .\run

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