Submission #1239802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239802		timeflew	Race (IOI11_race)	C++20	9 / 100	578 ms	46424 KiB

race

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

#ifdef debug
#define dbg(...) cerr<<#__VA_ARGS__<<" = ", de(__VA_ARGS__)
template<typename T>
void de(T t) {cerr<<t<<endl;}
template<typename T, typename ...U>
void de(T t, U...u) {cerr<<t<<", ", de(u...);}
#else
#define dbg(...)
#define endl "\n"
#endif

void usaco(string s) {
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int mxN=2e5;

vector<pair<int, int>> adj[mxN];
int n, k, siz[mxN], h[mxN][2], l[mxN];
bool cen[mxN];
map<ll, ll> mp;//dis, dis_min_cnt
vector<pair<ll, ll>> tmp;
ll ans=2e9;

void dfs(int v, int fa) {
    siz[v]=1;
    for(auto [u, w] : adj[v]) {
        if(u==fa||cen[u]) continue;
        dfs(u, v);
        siz[v]+=siz[u];
    }
}
 
int dfs1(int v, int fa, int sz) {
    for(auto [u, w] : adj[v]) {
        if(u==fa||cen[u]) continue;
        if(siz[u]>sz/2)
            return dfs1(u, v, sz);
    }
    return v;
}

void dfs2(int v, int fa, int cnt, ll dist) {
    if(mp.find(k-dist)!=mp.end()) {
        ans=min(ans, mp[k-dist]+cnt);
    }
    for(auto [u, w] : adj[v]) {
        if(u==fa||cen[u]) continue;
        tmp.push_back({cnt+1, dist+w});
        dfs2(u, v, cnt+1, dist+w);
    }
}

void cd(int v, int fa) {
    dfs(v, fa);
    int x=dfs1(v, fa, siz[v]);
    mp[0]=0;
    for(auto [u, w] : adj[x]) {
        if(cen[u]) continue;
        dfs2(u, x, 1, w);
        for(auto [cnt, t] : tmp) {
            if(mp.find(t)==mp.end()) {
                mp[t]=cnt;
            } else {
                mp[t]=min(mp[t], cnt);
            }
        }
        tmp.clear();
    }
    mp.clear();
    cen[x]=1;
    for(auto [u, w] : adj[x]) {
        if(cen[u]) continue;
        cd(u, x);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n=N, k=K;
    for(int i=0; i<N-1; i++) {
        h[i][0]=H[i][0];
        h[i][1]=H[i][1];
        l[i]=L[i];
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    cd(0, -1);
    if(ans==2e9) return -1;
    else return ans;
}

#ifdef debug
int main() {
    ios::sync_with_stdio(0); cin.tie(0); 
    cin>>n>>k;
    for(int i=0; i<n-1; i++) {
        cin>>h[i][0]>>h[i][1];
    }
    for(int i=0; i<n-1; i++) {
        cin>>l[i];  
    }
    cout<<best_path(n, k, h, l);
    return 0;
}
#endif
//rating below 2700 must be solved orzorzorz    
//4:30

Compilation message (stderr)

race.cpp: In function 'void usaco(std::string)':
race.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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