Submission #790443

#	Time	Username	Problem	Language	Result	Execution time	Memory
790443		merlin	Race (IOI11_race)	C++14	100 / 100	467 ms	42472 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define f first
#define s second
//https://ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103758/problem/B

void setIO(string name="") {
	cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

vector<vector<pair<int,int>>> sus; //vertex, dist
vector<int> mam,subtr;
vector<pair<int,int>> moje_d;
int SUBTR_SZ;
int K;

int dfs(int cur,int par = -1){
    subtr[cur] = 1;
    for(auto i : sus[cur])if(i.f != par && !mam[i.f]){
        subtr[cur] += dfs(i.f,cur);
    }
    return subtr[cur];
}

int find_centroid(int cur,int par = -1){
    for(auto i : sus[cur])if(i.f != par && !mam[i.f]){
        if(subtr[i.f]*2 > SUBTR_SZ) return find_centroid(i.f,cur);
    }
    return cur;
}

void calculate_d(int cur,unordered_map<int,int> &dists,int par = -1,int d = 0,int k = 0){
    if(d > K) return;
    if(dists.find(d) == dists.end()) dists[d] = k;
    else dists[d] = min(dists[d],k);
    for(auto i : sus[cur])if(i.f != par && !mam[i.f]){
        calculate_d(i.f,dists,cur,d + i.s,k+1);
    }
}

int solve(int cur){
    //cerr<<cur<<endl;
    int ans = 1<<30;
    SUBTR_SZ = dfs(cur);
    if(SUBTR_SZ == 1) return 1<<30;
    int centroid = find_centroid(cur);
    //cerr<<"centroid "<<centroid<<endl;
    //vector<int> moje_d(K+1,1<<30);
    //map<int,int> moje_d;
    mam[centroid] = 1;
    moje_d[0] = {0,centroid};
    for(auto i : sus[centroid])if(!mam[i.f]){
        unordered_map<int,int> tmp_d;
        calculate_d(i.f,tmp_d,centroid,i.s,1);
        //cerr<<"cur d: "<<i.f<<" ";
        //for(auto i : tmp_d)cerr<<i.f<<";"<<i.s<<" ";cerr<<endl;
        for(auto i : tmp_d)if(moje_d[K - i.f].s == centroid){
            ans = min(ans,moje_d[K - i.f].f + i.s);
        }
        for(auto i : tmp_d){
            if(moje_d[i.f].s == centroid)
                moje_d[i.f].f = min(moje_d[i.f].f,i.s);
            else
                moje_d[i.f] = {i.s,centroid};
        }
    }
    for(auto i : sus[centroid])if(!mam[i.f]){
        ans = min(ans,solve(i.f));
    }
    return ans;
}

int best_path(int n,int k,int edges[][2],int weights[]){
    sus.resize(n);
    mam.resize(n,0);
    subtr.resize(n);
    moje_d = vector<pair<int,int>>(k+1,{0,-1});
    K = k;
    for(int i = 0;i<n-1;i++){
        sus[edges[i][0]].push_back({edges[i][1],weights[i]});
        sus[edges[i][1]].push_back({edges[i][0],weights[i]});
    }
    int ans = solve(0);
    return ans == 1<<30 ? -1 : ans;
}

Compilation message (stderr)

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

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