Submission #395906

#	Time	Username	Problem	Language	Result	Execution time	Memory
395906		Jarif_Rahman	Race (IOI11_race)	C++17	9 / 100	595 ms	27592 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;

ll k;
vector<multiset<pair<ll, int>>> s;
vector<vector<pair<int, ll>>> v;
ll ans = 1e18;

void dfs(int nd, int ss, ll dis, int depth){
    for(auto [x, w]: v[nd]) if(x != ss) dfs(x, nd, dis+w, depth+1);
    int mx = -1, in = -1;
    for(auto [x, w]: v[nd]) if(x != ss){
        if(s[x].size() > mx){
            mx = s[x].size();
            in = x;
        }
    }
    if(in != -1) swap(s[nd], s[in]);
    for(auto [x, w]: v[nd]) if(x != ss){
        for(auto [d, dpt]: s[x]){
            dpt-=depth;
            d-=dis;
            ll dd = k-d;
            if(dd == 0){
                ans = min(ans, (ll)dpt);
            }
            else{
                auto it = s[nd].lower_bound(make_pair(dd, 0));
                if(it != s[nd].end() && it->f == dd){
                    ans = min(ans, dpt+(ll)(it->sc)-depth);
                }
            }
        }
        for(auto [d, dpt]: s[x]) s[nd].insert({d, dpt});
        s[x].clear();
    }
    s[nd].insert({dis, depth});
}

int best_path(int n, int k, int edges[][2], int w[]){
    ::k = k;
    v.resize(n);
    s.resize(n);
    for(int i = 0; i < n-1; i++){
        v[edges[i][0]].pb({edges[i][1], w[i]});
        v[edges[i][1]].pb({edges[i][0], w[i]});
    }
    dfs(0, -1, 0LL, 0);
    if(ans == inf) ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, ll, int)':
race.cpp:20:24: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |         if(s[x].size() > mx){
      |            ~~~~~~~~~~~~^~~~

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