Submission #395967

#	Time	Username	Problem	Language	Result	Execution time	Memory
395967		Jarif_Rahman	Race (IOI11_race)	C++17	21 / 100	3016 ms	24232 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 op_cnt = 0;
ll k;
vector<map<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 [d0, dpt0]: s[x]){
            op_cnt++;
            ll d = d0, dpt = dpt0;
            dpt-=depth;
            d-=dis;
            ll dd = k-d;
            if(dd == 0){
                ans = min(ans, dpt);
            }
            else{
                if(s[nd].find(dd+dis) != s[nd].end()){
                    ans = min(ans, dpt+s[nd][dd+dis]-depth);
                }
            }
        }
        for(auto [d, dpt]: s[x]){
            if(s[nd].find(d) == s[nd].end()) s[nd][d] = dpt;
            else s[nd][d] = min(s[nd][d], dpt);
        }
        cerr << op_cnt << "\n";
        s[x].clear();
    }
    if(s[nd].find(dis) == s[nd].end()) s[nd][dis] = depth;
    else s[nd][dis] = min(s[nd][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:21:24: warning: comparison of integer expressions of different signedness: 'std::map<long long int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |         if(s[x].size() > mx){
      |            ~~~~~~~~~~~~^~~~

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