제출 #395910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395910		Jarif_Rahman	경주 (Race) (IOI11_race)	C++17	0 / 100	1 ms	332 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 p: v[nd]) if(p.f != ss) dfs(p.f, nd, dis+p.sc, depth+1);
    int mx = -1, in = -1;
    for(auto p: v[nd]) if(p.f != ss){
        ll x = p.f, w = p.sc;
        if(s[x].size() > mx){
            mx = s[x].size();
            in = x;
        }
    }
    if(in != -1) swap(s[nd], s[in]);
    for(auto p: v[nd]) if(p.f != ss){
        ll x, w; tie(x, w) = p;
        for(auto pp: s[x]){
            ll dpt, d; tie(dpt, d) = p;
            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+dis, 0));
                if(it != s[nd].end() && it->f == dd+dis){
                    ans = min(ans, dpt+(ll)(it->sc)-depth);
                }
            }
        }
        for(auto pp: s[x]) s[nd].insert(pp);
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void dfs(int, int, ll, int)':
race.cpp:21: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]
   21 |         if(s[x].size() > mx){
      |            ~~~~~~~~~~~~^~~~
race.cpp:20:21: warning: unused variable 'w' [-Wunused-variable]
   20 |         ll x = p.f, w = p.sc;
      |                     ^
race.cpp:29:18: warning: variable 'pp' set but not used [-Wunused-but-set-variable]
   29 |         for(auto pp: s[x]){
      |                  ^~

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