Submission #854428

#	Time	Username	Problem	Language	Result	Execution time	Memory
854428		Onur_Ilgaz	Race (IOI11_race)	C++17	21 / 100	98 ms	30648 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
int ans, k;
vector <vector<pair<int, int> > > adj;
vector <map<int, int> > mp;
vector <int> depth, len;
 
void dfs(int node, int ata) {
    if(adj[node].size() == 1 and adj[node][0].first == ata) {
        mp[node].insert({0, 0});
        return;
    }
    // cerr<<"nodeata: "<<node<<" "<<ata<<"\n";
    int mx = 0, mxnode = -1, ww = -1;
    for(auto &[to, w]:adj[node]) {
        if(to == ata) continue;
        dfs(to, node);
        if((int)mp[to].size() > mx) {
            mxnode = to;
            mx = (int)mp[to].size();
            ww = w;
        }
    }
 
    mp[node].swap(mp[mxnode]);
    // do depth and len
    len[node] = len[mxnode] + ww;
    depth[node] = depth[mxnode] + 1;
 
    mp[node][0 - len[node]] = 0 - depth[node];
 
    if(mp[node].count(k - len[node])) {
        ans = min(ans, mp[node][k - len[node]] + depth[node]);
    }
  
    for(auto &[to, w]:adj[node]) {
        if(to == mxnode or to == ata) continue;
        for(auto it:mp[to]) {
            int realval = len[to] + it.first + w;
            int realdepth = depth[to] + it.second + 1;
            //check if k
            int need = (k - realval) - len[node];
            if(mp[node].count(need)) { // bu yanlışlıkla var olabilir?
                ans = min(ans, (mp[node][need] + depth[node] + realdepth));
            }
            // add it to map
            if(mp[node].count(realval - len[node]) ) 
                mp[node].insert({realval - len[node], realdepth - depth[node]});
            else 
                mp[node][realval - len[node]] = min(mp[node][realval - len[node]], realdepth - depth[node]);
        }
    }
}
 
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
    ans = inf, k = K;
    adj.clear(); adj.resize(N + 5);
    map <int, int> tmp;
    mp.clear(); mp.assign(N + 5, tmp);
    depth.clear(); depth.resize(N + 5);
    len.clear(); len.resize(N + 5);
    for(int i = 0; i < N - 1; i++) {
        int a = H[i][0], b = H[i][1], w = L[i];
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    dfs(0, -1);
    return (ans == inf) ? -1 : ans;
}

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