Submission #1315467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315467		mikolaj00	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<pair<ll, int>>> g; 
vector<bool> dead;
vector<int> subtree_size;
int ans = INT_MAX;

void compute_subtree_size(int u, int p)
{
    subtree_size[u] = 1;
    for (auto[w, v] : g[u])
    {
        if (v == p || dead[v])
            continue;
        
        compute_subtree_size(v, u);
        subtree_size[u] += subtree_size[v];
    }
}

int find_centroid(int u, int p)
{
    int mx_val = 0, mx_node = 0;
    for (auto[w, v] : g[u])
    {
        if (v == p || dead[v])
            continue;

        if (subtree_size[v] > mx_val)
        {
            mx_val = subtree_size[v];
            mx_node = v;
        }
    }

    if (mx_val <= (g.size()-1)/2)
        return u;
    else
        find_centroid(mx_node, u);
}

unordered_map<ll, int> mp;
vector<pair<ll, int>> vals;
void dfs(int u, int p, ll dist, int path)
{
    vals.push_back({dist, path});
    for (auto[w, v] : g[u])
    {
        if (v == p || dead[v])
            continue;

        dfs(v, u, dist+w, path+1);
    }
}

int ans = INT_MAX;
void decompose(int u, ll K)
{
    compute_subtree_size(u, 0);
    int centroid = find_centroid(u, 0);
    
    for (auto[w, v] : g[centroid])
    {
        if (dead[v])
            continue;

        dfs(v, centroid, w, 1);

        for (auto vals_i : vals)
            if (mp.count(K-vals_i.first))
                ans = min(ans, vals_i.second + mp[vals_i.first]);

        for (auto vals_i : vals)
            mp[vals_i.first] = min(mp[vals_i.first], vals_i.second);
        
        vals.clear();
    }

    if (mp.count(K))
        ans = min(ans, mp[K]);
    mp.clear();

    dead[centroid] = true;

    for (auto[w, v] : g[centroid])
    {
        if (dead[v])
            continue;

        decompose(v, K);
    }
}

int best_path(int N, ll K, int H[][2], ll L[])
{
    g = vector<vector<pair<ll, int>>>(N+1);
    for (int i = 0; i < N-1; i++)
    {
        g[H[i][0]].push_back({L[i], H[i][1]});
        g[H[i][1]].push_back({L[i], H[i][0]});
    }
}

Compilation message (stderr)

race.cpp:58:5: error: redefinition of 'int ans'
   58 | int ans = INT_MAX;
      |     ^~~
race.cpp:8:5: note: 'int ans' previously defined here
    8 | int ans = INT_MAX;
      |     ^~~
race.cpp: In function 'int best_path(int, ll, int (*)[2], ll*)':
race.cpp:104:1: warning: no return statement in function returning non-void [-Wreturn-type]
  104 | }
      | ^
race.cpp: In function 'int find_centroid(int, int)':
race.cpp:41:22: warning: control reaches end of non-void function [-Wreturn-type]
   41 |         find_centroid(mx_node, u);
      |         ~~~~~~~~~~~~~^~~~~~~~~~~~