Submission #447211

#	Time	Username	Problem	Language	Result	Execution time	Memory
447211		definitelynotmee	Race (IOI11_race)	C++98	100 / 100	1147 ms	62956 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,0);
    matrix<pii> grafo(n);
    for(int i = 0; i < n-1; i++)
        grafo[h[i][0]].push_back({h[i][1],l[i]}), grafo[h[i][1]].push_back({h[i][0],l[i]});
    
    int centroid;
    function<int(int,int,int)> dfsc = [&](int id, int last, int sizee){
        int ret = 1, maxi = 0;
        for(int i = 0; i < grafo[id].size(); i++){
            pii viz = grafo[id][i];
            if(viz.ff == last || check[viz.ff])
                continue;
            int cur = dfsc(viz.ff,id,sizee);
            ret+=cur;
            maxi = max(maxi,cur);
        }
        maxi = max(maxi,sizee-ret);
        if(maxi <= sizee/2)
            centroid =  id;
        return ret;
    };
    function<int(int,int,int,int,vector<pii>&v)> dfsd = [&](int id, int last, int ct, int dist, vector<pii>&v){
        if(dist > 1e7)
            dist = 1e7;
        v.push_back({ct,dist});
        int ret = 1;
        for(int i = 0; i < grafo[id].size(); i++){
            pii viz = grafo[id][i];
            if(viz.ff == last || check[viz.ff])
                continue;
            ret+=dfsd(viz.ff,id,ct+1,dist+viz.ss,v);

        }
        
        return ret;
    };
    int resp = INF;
    function<void(int,int)> findcentroid = [&](int id, int sizee){
        dfsc(id,-1,sizee);
        int curc = centroid;
        check[curc] = 1;
        map<int,int> m;

        for(int i = 0; i < grafo[curc].size(); i++){
            if(check[grafo[curc][i].ff])
                continue;
            vector<pii> dlist;
            int subtree = dfsd(grafo[curc][i].ff,-1,1,grafo[curc][i].ss,dlist);
            for(pii j : dlist){
                if(m.count(k-j.ss))
                    resp = min(resp,m[k-j.ss]+j.ff);
            }
            for(pii j : dlist){
                if(m.count(j.ss))
                    m[j.ss] = min(m[j.ss],j.ff);
                else m[j.ss] = j.ff;
            }
            findcentroid(grafo[curc][i].ff,subtree);
        }
        if(m.count(k))
            resp = min(resp,m[k]);
        
    };
    findcentroid(0,n);
    if(resp == INF)
        return -1;
    return resp;
}

Compilation message (stderr)

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

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