제출 #699913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699913		Alihan_8	Race (IOI11_race)	C++17	100 / 100	1082 ms	41592 KiB

race

#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
const int N = 1e6+1, inf = 1e9+1;
vector <vector<pair<int,int>>> g;
map <int,int> cnt;
int sub[N], used[N], K, res;
void get_size(int x, int par){
    sub[x] = 1;
    for ( auto [to, w]: g[x] ){
        if ( used[to] or to == par ) continue;
        get_size(to, x);
        sub[x] += sub[to];
    }
}
int get_ctr(int x, int par, int desired){
    for ( auto [to, w]: g[x] ){
        if ( used[to] or to == par ) continue;
        if ( desired <= sub[to] ) return get_ctr(to, x, desired);
    }
    return x;
}
void dfs(int x, int par, int depth, int len, bool add){
    if ( len > K ) return;
    if ( !add ){
        if ( len == K ) res = min(res, depth);
        else res = min(res, !cnt.count(K-len) ? inf : cnt[K-len]+depth);
    }
    else{
        if ( !cnt.count(len) ) cnt[len] = depth;
        else cnt[len] = min(cnt[len], depth);
    }
    for ( auto [to, w]: g[x] ){
        if ( used[to] or to == par ) continue;
        dfs(to, x, depth+1, len+w, add);
    }
}
void ctr_dec(int x){
    get_size(x, -1);
    int cur = get_ctr(x, -1, sub[x]/2);
    cnt.clear();
    used[cur] = true;
    for ( auto [to, w]: g[cur] ){
        if ( used[to] ) continue;
        dfs(to, -1, 1, w, false);
        dfs(to, -1, 1, w, true);
    }
    for ( auto [to, w]: g[cur] ){
        if ( used[to] ) continue;
        ctr_dec(to);
    }
}
int best_path(int n, int k, int h[][2], int L[]){
    g.resize(n);
    for ( int i = 0; i+1 < n; i++ ){
        g[h[i][0]].pb({h[i][1], L[i]});
        g[h[i][1]].pb({h[i][0], L[i]});
    }
    K = k; res = inf;
    ctr_dec(0);
    if ( res == inf ) res = -1;
    return res;
}

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

race.cpp: In function 'void IO(std::string)':
race.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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