Submission #1200031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200031		quocbaoo	Evacuation plan (IZhO18_plan)	C++20	100 / 100	894 ms	38856 KiB

plan

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
ll dp[100004];vector<pair<int,ll>> g[100005];
int par[100004],sz[100005],a[500005],b[500005],l[500005],r[500005],ans[500005],dd[100004];
bool cmp(pair<int,int> u1,pair<int,int> v1){
    return u1.fi>v1.fi;
}
int f(int z){
    if (z==par[z]) return z;
    int p=f(par[z]);
    return par[z]=p;
}
void gop(int u1,int v1){
    u1=f(u1);v1=f(v1);
    if (u1==v1) return ;
    if (sz[v1]>sz[u1]) swap(u1,v1);
    sz[u1]+=sz[v1];
    par[v1]=u1;
}
int main(){
    if (fopen("seqdiv.inp","r")){
        freopen("seqdiv.inp","r",stdin);
        freopen("seqdiv.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;i++){
        ll u,v,w;cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    multiset<tuple<ll,int>> st;
    int k;cin>>k;memset(dp,0x3f,sizeof(dp));
    for (int i=1;i<=k;i++){
        int s;cin>>s;
        st.insert({0,s});dp[s]=0;
    }
    while (!st.empty()){
        auto [qd,bd]=*st.begin();st.erase(st.begin());
        if (dp[bd]!=qd) continue;
        for (auto j:g[bd]){
            if (qd+j.se<dp[j.fi]){
                dp[j.fi]=qd+j.se;
                st.insert({dp[j.fi],j.fi});
            }
        }
    }
    int q;cin>>q;vector<pair<int,int>> v1;
    for (int i=1;i<=q;i++) cin>>a[i]>>b[i],l[i]=0,r[i]=1e9,ans[i]=-1;
    for (int i=1;i<=n;i++)
        v1.push_back({dp[i],i});
    v1.push_back({-1,n+1});
    sort(v1.begin(),v1.end());vector<pair<int,int>> v;
    while (true){
        v.clear();
        for (int i=1;i<=q;i++){
            if (l[i]>r[i]) continue;
            v.push_back({(l[i]+r[i])/2,i});
        }
        if (v.size()==0) break;
        sort(v.begin(),v.end(),cmp);
        for (int i=1;i<=n;i++) dd[i]=false,par[i]=i,sz[i]=1;
        int d=0;
        for (int i=v1.size()-1;i>=0;i--){
//                cout<<v1[i].fi<<" "<<v1[i].se<<endl;
            while (d<v.size()&&v1[i].fi<v[d].fi){
//                if (v[d].se==4) cout<<v[d].fi<<" "<<v1[i].fi<<" "<<f(1)<<" "<<f(5)<<endl;
                if (f(a[v[d].se])==f(b[v[d].se])){
                    ans[v[d].se]=v[d].fi;l[v[d].se]=v[d].fi+1;
                }
                else r[v[d].se]=v[d].fi-1;
                d++;
            }
            for (auto j:g[v1[i].se]){
                if (dd[j.fi]==true){
                    gop(j.fi,v1[i].se);
                }
            }
            dd[v1[i].se]=true;

        }
    }
    for (int i=1;i<=q;i++) cout<<ans[i]<<" ";
}

Compilation message (stderr)

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

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