Submission #888435

#	Time	Username	Problem	Language	Result	Execution time	Memory
888435		TitanSlayer	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ld long double
#define vv vector
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define mod 1000000007

typedef pair<ll, ll> pll;
typedef vv<ll> vll;
typedef vv<ld> vld;
typedef vv<pll> vpll;
typedef set<ll>::iterator sitr;

#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
///////////////////////////////////

ll n, k, ans = 1e9;
vector<map<ll, ll>> m(200005);
vv<vpll> v(200005);
pll offset[200005];

void dfs(ll node, ll par)
{
    // cout << node << " " << par << endl;
    m[node][0] = 0;
    offset[node] = {0, 0};
    for (auto child : v[node])
    {
        if (child.F == par)
            continue;
        dfs(child.F, node);

        offset[child.F].F += child.S;
        offset[child.F].S += 1;
        if (m[child.F].size() > m[node].size())
        {
            swap(m[child.F], m[node]);
            swap(offset[child.F], offset[node]);
            // cout << child.F << " swaps " << node << endl;
        }
        // else
            // cout << child.F << " Not swaps " << node << endl;

        for (auto itr_child : m[child.F])
        {
            ll dist = itr_child.F + offset[child.F].F;
            ll cnt = itr_child.S + offset[child.F].S;
            // cout << dist << " " << cnt << endl;
            auto itr_par = m[node].find(k - dist - offset[node].F);
            if (itr_par != m[node].end())
                ans = min(ans, cnt + itr_par->second + offset[node].S);
        }

        for (auto itr_child : m[child.F])
        {
            ll dist = itr_child.F + offset[child.F].F - offset[node].F;
            ll cnt = itr_child.S + offset[child.F].S - offset[node].S;

            auto itr_par = m[node].find(dist);
            if (itr_par != m[node].end())
                m[node][dist] = min(cnt, m[node][dist]);
            else
                m[node][dist] = cnt;
        }

        // for (auto i1 : m[node])
        //     cout << i1.F << "|" << i1.S << " ";
        // cout << " : " << offset[node].F << "|" << offset[node].S;
        // cout << endl;
        // for (auto i1 : m[child.F])
        //     cout << i1.F << "|" << i1.S << " ";
        // cout << " : " << offset[child.F].F << "|" << offset[child.F].S;

        // cout << endl;
        // cout << endl;
    }
}

int main()
{
    fastio;
    ll T = 1;
    // cin >> T;
    while (T--)
    {
        ll i, j, a, b, c;
        cin >> n >> k;

        for (i = 0; i < n - 1; i++)
        {
            cin >> a >> b >> c;
            v[a].pb({b, c});
            v[b].pb({a, c});
        }

        dfs(0, -1);

        if (ans == 1e9)
            ans = -1;
        cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:92:15: warning: unused variable 'j' [-Wunused-variable]
   92 |         ll i, j, a, b, c;
      |               ^
/usr/bin/ld: /tmp/ccYtECyJ.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyrucOM.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccyrucOM.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status