제출 #395912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395912		Jarif_Rahman	경주 (Race) (IOI11_race)	C++17	21 / 100	727 ms	262148 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;
const int lim = 2e5+1;

ll k;
set<pair<ll, int>> s[lim];
vector<pair<int, ll>> v[lim];
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+dis, 0));
                if(it != s[nd].end() && it->f == dd+dis){
                    ans = min(ans, dpt+(ll)(it->sc)-depth);
                }
            }
        }
        for(auto [d, dpt]: s[x]) s[nd].insert({d, dpt});
    }
    s[nd].insert({dis, depth});
}

int best_path(int n, int k, int edges[][2], int w[]){
    ::k = k;
    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::set<std::pair<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