Submission #447196

#	Time	Username	Problem	Language	Result	Execution time	Memory
447196		definitelynotmee	Race (IOI11_race)	C++98	0 / 100	1 ms	332 KiB

race

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;



int best_path(int n, int k, int h[][2], int l[]){

    vector<int> check(n+1,0);
    matrix<int> grafo(n+1), peso(n+1);
    for(int i = 0; i < n-1; i++)
        grafo[h[i][0]].push_back(h[i][1]), grafo[h[i][1]].push_back(h[i][0]), peso[h[i][0]].push_back(l[i]), peso[h[i][1]].push_back(l[i]);

    int centroid;
    function<int(int,int,int,int,int,vector<pii>&)> dfs = [&](int id, int last, int sizee, int dist, int count, vector<pii>&v){
        if(dist == 0)
            dist--;
        else v.push_back({count,dist});
        int ret = 1, maxi = 0;
        for(int i = 0; i < grafo[id].size(); i++){
            if(grafo[id][i] == last || check[grafo[id][i]])
                continue;
            int cur = dfs(grafo[id][i],id,sizee,min(dist+peso[id][i],(int)1e7),count + 1,v);
            maxi = max(maxi, cur);
            ret +=cur;
        }
        maxi = max(maxi,sizee-ret);
        if(maxi <= sizee/2)
            centroid = id;
        return ret;
    };
    vector<pii> nullv;
    int resp = INF;
    function<int(int,int)> findcentroid = [&](int id, int sizee){
        dfs(id,0,sizee,0,0,nullv);
        int curcen = centroid;
        check[curcen] = 1;
        unordered_map<int,int> m;
        for(int i = 0; i < grafo[curcen].size(); i++){
            if(check[grafo[curcen][i]])
                continue;
            vector<pii> v;
            int subtree = dfs(grafo[curcen][i],0,0,peso[curcen][i],1,v);
            for(pii j : v){
                if(m.count(k-j.ss)){
                    resp = min(resp, m[k-j.ss] + j.ff);
                }
            }
            for(pii j : v){
                if(m.count(j.ss)){
                    m[j.ss] = min(m[j.ss], j.ff);
                } else m[j.ss] = j.ff;
            }
            findcentroid(grafo[curcen][i],subtree);
        }
        if(m.count(k))
            resp = min(resp,m[k]);
        return curcen;
    };
    findcentroid(1,n);
    return resp;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i = 0; i < grafo[id].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~
race.cpp: In lambda function:
race.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0; i < grafo[curcen].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~

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