Submission #1312346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312346		coderg	Race (IOI11_race)	C++20	100 / 100	237 ms	30324 KiB

race

 #include "bits/stdc++.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;

const int maxn=1000005;
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;

int mnedges[maxn],ans,k;

struct Centroid{
    int n;
    vector<vector<pii> > adj;
    vector<int> siz;
    vector<bool> removed;
    int cnt[20][2];
    ll tot;
    Centroid(int nodes) : n(nodes) {
        adj.resize(n+1);
        removed.assign(n,0);
        siz.resize(n);
    }
    void add(int u,int v,int w){
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    void calcsiz(int u,int p){
        siz[u]=1;
        for(auto& e:adj[u]){
            int v=e.fi;
            if(v!=p && !removed[v]){
                calcsiz(v,u);
                siz[u]+=siz[v];
            }
        }
    }
    int findcentroid(int u,int p,int totnodes){
        for(auto& e:adj[u]){
            int v=e.fi;
            if(v!=p && !removed[v] && siz[v]>totnodes/2)return findcentroid(v,u,totnodes);
        }
        return u;
    }
    vector<pii> pathnodes;
    void getpathnodes(int u,int p,int curdist,int curedges){
        if(curdist>k)return;
        pathnodes.pb({curdist,curedges});
        for(auto& e:adj[u]){
            int v=e.fi,w=e.se;
            if(v!=p && !removed[v])getpathnodes(v,u,curdist+w,curedges+1);
        }
    }
    //this function changes for every problem
    void descompose(int u){
        calcsiz(u,-1);
        int cen=findcentroid(u,-1,siz[u]);
        mnedges[0]=0;
        vector<int> modified;
        modified.pb(0);
        removed[cen]=1;
        for(auto& e:adj[cen]){
            int v=e.fi,w=e.se;
            if(!removed[v]){
                pathnodes.clear();
                getpathnodes(v,cen,w,1);
                for(auto& p:pathnodes){
                    int dist=p.fi,edges=p.se;
                    int target=k-dist;
                    if(target>=0 && mnedges[target]!=inf)ans=min(ans,edges+mnedges[target]);
                }
                for(auto& p:pathnodes){
                    int dist=p.fi,edges=p.se;
                    if(dist<=k){
                        if(mnedges[dist]==inf){
                            mnedges[dist]=edges;
                            modified.pb(dist);
                        }else{
                            mnedges[dist]=min(mnedges[dist],edges);
                            if(dist!=0)modified.pb(dist);
                        }
                    }
                }
            }
        }
        for(int idx:modified)mnedges[idx]=inf;
        for(auto& e:adj[cen]){
            int v=e.fi;
            if(!removed[v])descompose(v);
        }
    }
};

int best_path(int N,int K,int H[][2],int L[]){
    ans=inf;
    k=K;
    F(i,0,k+1)mnedges[i]=inf;
    Centroid cd(N);
    F(i,0,N-1)cd.add(H[i][0],H[i][1],L[i]);
    cd.descompose(0);
    if(ans==inf)return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void setIO(std::string)':
race.cpp:10:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:10:98: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57