Submission #447206

#	Time	Username	Problem	Language	Result	Execution time	Memory
447206		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<ll> check(n+1,0);
    matrix<ll> 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<ll(ll,ll,ll,ll,ll,vector<pll>&)> dfs = [&](ll id, ll last, ll sizee, ll dist, ll count, vector<pll>&v){
        if(dist != 0)
            v.push_back({count,dist});
        ll ret = 1, maxi = 0;
        for(int i = 0; i < grafo[id].size(); i++){
            if(grafo[id][i] == last || check[grafo[id][i]])
                continue;
            ll cur = dfs(grafo[id][i],id,sizee,dist == 0 ? 0 : dist+peso[id][i],count + 1,v);
            maxi = max(maxi, cur);
            ret +=cur;
        }
        maxi = max(maxi,sizee-ret);
        if(maxi <= sizee/2)
            centroid = id;
        return ret;
    };
    vector<pll> nullv;
    ll resp = INF;
    function<ll(ll,ll)> findcentroid = [&](ll id, ll sizee){
        dfs(id,-1,sizee,0,0,nullv);
        int curcen = centroid;
        check[curcen] = 1;
        map<ll,ll> m;
        for(int i = 0; i < grafo[curcen].size(); i++){
            if(check[grafo[curcen][i]])
                continue;
            vector<pll> v;
            int subtree = dfs(grafo[curcen][i],-1,0,peso[curcen][i],1,v);
            for(pll j : v){
                if(m.count(k-j.ss)){
                    resp = min(resp, m[k-j.ss] + j.ff);
                }
            }
            for(pll 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(0,n);
    if(resp == INF)
        return -1;
    if(resp == 0)
        exit(1);
    return resp;
}

Compilation message (stderr)

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