제출 #1293407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293407		quocbaoo	Evacuation plan (IZhO18_plan)	C++20	100 / 100	396 ms	81956 KiB

plan

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e5;
int h[N*2+5],a[N*4+5],par[N*4+5][22],dp[N*2+5];vector<int> ad[N*2+5];
int lg[N*4+5],pa[N*2+5],cnt=0,bd[N*2+6];vector<pair<int,int>> g[N+5];
struct Node{
    int fi,se,ba;
};
vector<Node> ok;int dem=0;
bool cmp(Node u1,Node v1){
    return u1.ba>v1.ba;
}
int f(int u){
    if (u==pa[u]) return u;
    int p=f(pa[u]);
    return pa[u]=p;
}
void gop(int u,int v,int w){
    u=f(u);v=f(v);
    if (u==v) return;
    dem++;
    pa[dem]=dem;pa[u]=dem;pa[v]=dem;
    dp[dem]=w;
    ad[dem].push_back(u);ad[dem].push_back(v);
}
void dfs(int i,int pa){
    cnt++;bd[i]=cnt;a[cnt]=i;
    for (auto j:ad[i]){
        if (j==pa) continue;
        h[j]=h[i]+1;
        dfs(j,i);
        cnt++;a[cnt]=i;
    }
}
int mH(int u,int v){
    if (h[u]<h[v]) return u;return v;
}
int get(int u,int v){
    if (u>v) swap(u,v);
    int k=lg[v-u+1];
    return mH(par[u][k],par[v-(1<<k)+1][k]);
}
int main(){
    if (fopen("plan.inp","r")){
        freopen("plan.inp","r",stdin);
        freopen("plan.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    vector<pair<int,int>> vec;
    for (int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        vec.push_back({u,v});
    }
    for (int i=1;i<=n*2;i++) pa[i]=i;
    int k;cin>>k;
    memset(dp,0x3f,sizeof(dp));
    set<tuple<int,int>> st;
    for (int i=1;i<=k;i++){
        cin>>a[i];st.insert({0,a[i]});
        dp[a[i]]=0;
    }
    while (!st.empty()){
        auto [qd,bd]=*st.begin();st.erase(st.begin());
        if (dp[bd]!=qd) continue;
        for (auto j:g[bd]){
            if (j.se+qd<dp[j.fi]){
                dp[j.fi]=j.se+qd;
                st.insert({dp[j.fi],j.fi});
            }
        }
    }
    for (auto j:vec){
        ok.push_back({j.fi,j.se,min(dp[j.fi],dp[j.se])});
    }
    sort(ok.begin(),ok.end(),cmp);
    dem=n;
    for (Node j:ok){
        gop(j.fi,j.se,j.ba);
//        cout<<j.fi<<" "<<j.se<<" "<<j.ba<<endl;
    }
    dfs(dem,dem);
    for (int i=1;i<=cnt;i++) par[i][0]=a[i];
    for (int i=2;i<=cnt;i++) lg[i]=lg[i/2]+1;
    for (int j=1;j<=20;j++){
        for (int i=1;i<=cnt;i++){
            if (i+(1<<(j-1))>cnt) continue;
            par[i][j]=mH(par[i][j-1],par[i+(1<<(j-1))][j-1]);
        }
    }
    int q;cin>>q;
    while (q--){
        int u,v;cin>>u>>v;
//        cout<<bd[u]<<" "<<bd[v]<<endl;
        cout<<dp[get(bd[u],bd[v])]<<'\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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