Submission #853978

#	Time	Username	Problem	Language	Result	Execution time	Memory
853978		Onur_Ilgaz	Race (IOI11_race)	C++17	0 / 100	1 ms	2396 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]);
    // change to depth and valdepth
    len[node] = len[mxnode] + ww;
    depth[node] = depth[mxnode] + 1;
    mp[node].insert({0 - len[node], 0 - depth[node]});
    if(mp[node].count(k - len[node])) {
        ans = min(ans, mp[node][k - len[node]] + depth[node]);
    }

    // cerr<<"check "<<node<<" "<<mxnode<<" "<<len[node]<<" "<<depth[node]<<":\n";
    for(auto it:mp[node]) {
        // cerr<<it.first<<" "<<it.second<<"\n";
    }

    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]);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    ans = inf, k = K;
    adj.clear(); adj.resize(N + 5);
    map <int, int> tmp;
    mp.clear(); mp.assign(N + 5, tmp);
    // try
    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;
}

// #define MAX_N 500000

// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;

// inline 
// void my_assert(int e) {if (!e) abort();}

// void read_input()
// {
//   int i;
//   my_assert(2==scanf("%lld %lld",&N,&K));
//   for(i=0; i<N-1; i++)
//     my_assert(3==scanf("%lld %lld %lld",&H[i][0],&H[i][1],&L[i]));
//   my_assert(1==scanf("%lld",&solution));
// }

// int32_t main()
// {
//   int ans;
//   read_input();
//   ans = best_path(N,K,H,L);
//   if(ans==solution)
//     printf("Correct.\n");
//   else
//     printf("Incorrect. Returned %lld, Expected %lld.\n",ans,solution);

//   return 0;
// }

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:39:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   39 |     for(auto it:mp[node]) {
      |              ^~

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