Submission #1126980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126980		KK_1729	Race (IOI11_race)	C++17	100 / 100	440 ms	82084 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;



// #define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

int min(int x, int y){
  if (x < y) return x;
  return y;
}


void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

vector<map<int, int>> m;
vector<int> root;
vector<int> dist;
vector<vector<pair<int, int>>> graph;

int answer = 100; int T;
set<int> q;
void dfs(int s, int p){
    int target = T+2*root[s];
    
    for (auto [node, weight]: graph[s]){
        if (node == p) continue;

        dfs(node, s);

        if (m[node].size() > m[s].size()) swap(m[node], m[s]);
        
        for (auto x: m[node]){
          // cout << target-x.first << endl;
          if (m[s].find(target-x.first) != m[s].end()){
            answer = min(answer, m[s][target-x.first] + x.second - 2*dist[s]);
            q.insert(m[s][target-x.first] + x.second - 2*dist[s]);
            // cout << "a" << answer << endl;
          }
        }

        for (auto x: m[node]){
          if (x.second == 0) continue;
          // if (s == 1 && x.first == 9) cout << node << endl;
          if (m[s].find(x.first) == m[s].end()){
            m[s].insert(x);
          }else{
            m[s][x.first] = min(m[s][x.first], x.second);
          }
        }
    }

    int targ = T+root[s];
    if (m[s].find(targ) != m[s].end()){
      // if (s == 1) cout <<"a" << target << endl;
      q.insert(m[s][targ]-dist[s]);
      // cout << s << endl;
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    T = K;
    // cout << "a" << endl;
    dist.resize(N+1);
    root.resize(N+1);
    graph.resize(N+1);
    m.resize(N+1);
    FOR(i,0,N-1){
        graph[H[i][0]].pb({H[i][1], L[i]});
        graph[H[i][1]].pb({H[i][0], L[i]});
    }
    stack<int> s;
    s.push(0);
    vector<int> visited(N+1);
    while (!s.empty()){
        int current = s.top();
        s.pop();
        if (visited[current]) continue;

        for (auto [x, w]: graph[current]){
            if (visited[x]) continue;
            root[x] = root[current]+w;
            dist[x] = dist[current]+1;
            m[x][root[x]] = dist[x];
            s.push(x);
        }
        visited[current] = 1;
    }
    // printVector(root);
    // printVector(dist);
    dfs(0, -1);
    if (!q.size()) return -1;
    
    // for (auto x: q){
    //   cout << x << endl;
    // }
    return *q.begin();
}

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