Submission #419304

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

race

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
struct ura{
    int x, c;
};
vector <ura> g[N];
int vc[K];
int sz[N], viz[N];
int n, k; int minim = K;
void dfsSize(int nod, int dad = -1)
{
    sz[nod] = 1;
    for (auto son : g[nod])
    {
        if (son.x == dad || viz[son.x])
            continue;
        dfsSize(son.x, nod);
        sz[nod] += sz[son.x];
    }
}
map <int, int> mp2;
int centroid(int nod, int dad, int newN)
{
    for (auto son : g[nod])
    {
        if (son.x == dad || viz[son.x])
            continue;
        if (sz[son.x] > newN / 2)
            return centroid(son.x, nod, newN);
    }
    return nod;
}
void dfs(int nod, int dad, int sum, int l)
{
    if (sum > k)
        return;
    if (mp2[sum])
        mp2[sum] = min(mp2[sum], l);
    else
        mp2[sum] = l;
    for (auto son : g[nod])
    {
        if (son.x == dad || viz[son.x])
            continue;
        dfs(son.x, nod, sum + son.c, l + 1);
    }
}
void divide(int root)
{
    dfsSize(root);
    int mid = centroid(root, -1, sz[root]);
    viz[mid] = 1;
    map <int, int> mp;
    for (auto son : g[mid])
    {
        int x = son.x;
        if (viz[x])
            continue;
        mp2.clear();
        dfs(x, mid, son.c, 1);
        for (auto it : mp2)
        {
            if (it.first == k)
                minim = min(minim, it.second);
            if (mp.count(k - it.first) == 0)
                continue;
            minim = min(minim, it.second + mp[k - it.first]);
        }
        for (auto it : mp2)
        {
            int beb = it.first;
            if (mp[beb] == 0)
                mp[beb] = mp2[beb];
            else
                mp[beb] = min(mp[beb], mp2[beb]);
        }
    }
    for (auto son : g[mid])
        if (viz[son.x] == 0)
            divide(son.x);
}
int best_path(int nn, int kk, int h[][2], int l[])
{
    int i;
    n = nn;
    k = kk;
    for (i = 0; i < n - 1; i++)
    {
        int a = h[i][0];
        int b = h[i][1];
        g[a].push_back({b, l[i]});
        g[b].push_back({a, l[i]});
    }
    divide(0);
    if (minim == K)
        minim = -1;
    return minim;
}
int nnn, kkk;
int h[N][2];
int l[N];

int main()
{
    int nnn, kkk;
    cin >> nnn >> kkk;
    for (int i = 0; i < nnn - 1; i++)
    {
        cin >> h[i][0];
        cin >> h[i][1];
        cin >> l[i];
    }
    cout << best_path(nnn, kkk, h, l);
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccbnGPee.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccSMwNpd.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status