제출 #1269301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269301		uranium235	Race (IOI11_race)	C++17	9 / 100	190 ms	74408 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 10000000;

int best_path(int n, int k, int h[][2], int l[]) {
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }
    vector<int> weight(n), depth(n);
    auto dfs1 = [&](int v, int p, int w, int d, auto &&self) -> void {
        depth[v] = d;
        weight[v] = w;
        for (pair<int, int> &i : adj[v]) {
            if (i.first != p) self(i.first, v, min(inf, w + i.second), d + 1, self);
        }
    };
    dfs1(0, -1, 0, 0, dfs1);
    vector<map<int, int>> maps(n);
    int ans = INT32_MAX;
    auto dfs2 = [&](int v, int p, auto &&self) -> void {
        maps[v][weight[v]] = depth[v]   ;
        for (pair<int, int> &i : adj[v]) {
            if (i.first != p) {
                self(i.first, v, self);
                if (maps[i.first].size() > maps[v].size()) swap(maps[i.first], maps[v]);

                for (map<int, int>::iterator iter = maps[i.first].begin(); iter != maps[i.first].end(); iter++) {
                    map<int, int>::iterator found = maps[v].find(k + 2 * weight[v] - iter->first);
                    if (found != maps[v].end()) {
                        ans = min(ans, iter->second + found->second - 2 * depth[v]);
                        // cout << "found " << iter->second << " " << found->second << endl;
                    }
                }

                for (map<int, int>::iterator iter = maps[i.first].begin(); iter != maps[i.first].end(); iter++) {
                    map<int, int>::iterator other = maps[v].find(iter->first);
                    // cout << v << " merging " << iter->first << "->" << iter->second << endl;
                    if (other != maps[v].end()) {
                        if (other->second > iter->second) other->second = iter->second;
                    } else maps[v][iter->first] = iter->second;
                }

            }
        }
        // cout << "vis " << v << endl;
        // for (map<int, int>::iterator iter = maps[v].begin(); iter != maps[v].end(); iter++) {
            // cout << "map " << v << " " << iter->first << "->" << iter->second << endl;
        // }
    };
    dfs2(0, -1, dfs2);

    return (ans == INT32_MAX) ? -1 : ans;
}

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