제출 #1142284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142284		dragdam	Race (IOI11_race)	C++17	9 / 100	97 ms	33604 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5+5;
const int inf = 2e9;


int n, r;
vector<array<int,2>> g[MAXN];
int ans;
map<int,int> m[MAXN];
array<int,2> o[MAXN];

void dfs(int x, int p){
    for(auto k : g[x]){
        if(k[0]==p) continue;
        dfs(k[0],x);
    }
    for(auto [k,w] : g[x]){
        if(k==p) continue;
        o[k][0] += w;
        o[k][1] += 1;
        m[k][w-o[k][0]] = 1-o[k][1];
        if(m[k].size() > m[x].size()){
            swap(m[k], m[x]);
            swap(o[k], o[x]);
        }
        //cout << x << ' ' << k << '\n';
        for(pair<int,int> p : m[k]){
            //cout << p.first << ' ' << p.second << ' ' << r-p.first-o[x][0]-o[k][0] << '\n';
            if(m[x].find(r-p.first-o[x][0]-o[k][0])!=m[x].end()){
                ans = min(ans, p.second+m[x][r-p.first-o[x][0]-o[k][0]]) + o[k][1] + o[x][1];
            }
            p.first = p.first+o[k][0]-o[x][0];
            m[x][p.first] = min(p.second+o[k][1], (m[x][p.first] ? m[x][p.first] : inf));
        }
        //cout << o[x][0] << ' ' << o[x][1] << '\n';
        //for(auto p : m[x]) cout << p.first << " : " << p.second << '\n'; cout << '\n';
    }
    if(m[x].find(r-o[x][0])!=m[x].end()) ans = min(ans, m[x][r-o[x][0]] + o[x][1]);
    /*cout << x << ' ' << o[x][0] << ' ' << o[x][1] << '\n';
    for(auto p : m[x]) cout << p.first << ' ' << p.second << '\n'; cout << '\n';*/
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
    n = N; r = K;
    ans = inf;
    for(int i = 0; i < n; ++i){
        g[i].clear();
        m[i].clear();
        o[i] = {0,0};
    }
    for(int i = 0; i < n-1; ++i){
        int x = H[i][0], y = H[i][1], w = L[i];
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dfs(0,0);
    return (ans==inf ? -1 : ans);
}

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