Submission #831565

#	Time	Username	Problem	Language	Result	Execution time	Memory
831565		Cookie	Evacuation plan (IZhO18_plan)	C++14	100 / 100	543 ms	54468 KiB

plan

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const int mxn = 2e5 + 5;
const ll inf = 1e9;
struct DSU{
    vt<pii>past_p, past_sz;
    vt<int>checkpoint;
    int p[mxn + 1], sz[mxn + 1];
    void init(){
        for(int i = 1; i <= mxn; i++){
            p[i] = i; sz[i]  = 1; 
        }
        past_sz.clear(); past_p.clear(); checkpoint.clear();
    }
    int fp(int a){
        if(p[a] == a)return(a);
        return(fp(p[a]));
    }
    bool check(int u, int v){
        return(fp(u) == fp(v));
    }
    void unon(int a, int b){
        a = fp(a); b = fp(b);
        if(sz[a] < sz[b])swap(a, b);
        past_sz.pb({a, sz[a]}); past_p.pb({b, p[b]}); 
        if(a != b){
            sz[a] += sz[b]; p[b] = a;
        }
    }
    void rollback(){
        //int before = p[past_p.back().fi], after = past_p.back().se;
        //if(before != past_p.back().fi && after == past_p.back().fi)cnt++;
        p[past_p.back().fi] = past_p.back().se; past_p.pop_back();
        sz[past_sz.back().fi] = past_sz.back().se; past_sz.pop_back();
    }
    void save(){
        checkpoint.pb(past_sz.size());
    }
    void to_last(){
        while(past_sz.size() != checkpoint.back())rollback();
        checkpoint.pop_back();
    }
};
DSU dsu;
int n, m, k;
int dis[mxn + 1], a[mxn + 1], ans[mxn + 1], s[mxn + 1], t[mxn + 1];
bool ok[mxn + 1];
vt<pii>adj[mxn + 1];
bool cmp(int x, int y){
    return(dis[x] > dis[y]);
}
vt<int>comp;

void sp(){
    priority_queue<pll, vt<pll>, greater<pll>>pq; 
    forr(i, 1,  n + 1)dis[i] = inf;
    forr(i, 0, k){
        dis[a[i]] = 0; pq.push({dis[a[i]], a[i]});
    }
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        if(dis[u] != dd)continue;
        for(auto [v, w]: adj[u]){
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
    
}
void solve(int l, int r, vt<int>cand){
    if(l > r)return;
    if(l == r){
        for(auto i: cand)ans[i] = l;
        return;
    }
    dsu.save();
    int mid = (l + r) >> 1;
    for(int i = l; i <= mid; i++){
        ok[comp[i]] = 1;
    }
    for(int i = l; i <= mid; i++){
        for(auto [v, w]: adj[comp[i]]){
            if(ok[v]){
                dsu.unon(comp[i], v);
            }
        }
    }
    vt<int>yes, no;
    for(auto i: cand){
        if(dsu.check(s[i], t[i])){
            yes.pb(i);
        }else{
            no.pb(i);
        }
    }
    solve(mid + 1, r, no);
    for(int i = l; i <= mid; i++)ok[comp[i]] = 0;
    dsu.to_last();
    solve(l, mid, yes);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    dsu.init();
    forr(i, 0, m){
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w}); adj[v].pb({u, w});
    }
    cin >> k;
    forr(i, 0, k)cin >> a[i];
    sp();
    for(int i = 1; i <= n; i++)comp.pb(i);
    vt<int>all;
    sort(comp.begin(), comp.end(), cmp);
    int q; cin >> q;
    forr(i, 0, q){
        cin >> s[i] >> t[i];
        all.pb(i);
    }
    solve(0, sz(comp) - 1, all);
    forr(i, 0, q)cout << dis[comp[ans[i]]] << "\n";
    return(0);
}

Compilation message (stderr)

plan.cpp: In member function 'void DSU::to_last()':
plan.cpp:58:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   58 |         while(past_sz.size() != checkpoint.back())rollback();
      |               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
plan.cpp: In function 'void sp()':
plan.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
plan.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         for(auto [v, w]: adj[u]){
      |                  ^
plan.cpp: In function 'void solve(int, int, std::vector<int>)':
plan.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for(auto [v, w]: adj[comp[i]]){
      |                  ^

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