Submission #111783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111783	2019-05-16T07:16:34 Z	Mercenary	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include<bits/stdc++.h>
 
using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 2e5 + 5;
typedef pair<int,int> tpair;
int n , sz[maxn] , h[maxn] , k;
int res = maxn;
vector<tpair> v[maxn];
unordered_map<ll,int> *vec[maxn];
ll dep[maxn];
void DFS1(int u , int p)
{
    sz[u] = 1;
    for(tpair c : v[u])
    {
        if(p == c.first)continue;
        h[c.first] = h[u] + 1;
        dep[c.first] = dep[u] + c.second;
        DFS1(c.first,u);
        sz[u] += sz[c.first];
    }
}
void add(unordered_map<ll,int> & s , int h1 , ll d1 , int& h , ll& d , int type)
{
    if(type == 1)
    {
        ll need = k - d1 + 2 * d;
        if(!s.count(need))return;
        res = min(res ,s[need] + h1 - 2 * h);
    }
    else {
        if(!s.count(d1))
        {
            s[d1] = h1;
            return;
        }
        int tmp = s[d1];
        if(tmp > h1)s[d1] = h1;
    }
}
void DSU(int u , int p)
{
    int bigchild = -1;
    for(auto c : v[u])
        if(c.first != p && (bigchild == -1 || sz[bigchild] < sz[c.first]))
            bigchild = c.first;
    for(auto c : v[u])
        if(c.first != p && c.first != bigchild)
            DSU(c.first , u);
    if(bigchild != -1)
    {
        DSU(bigchild , u);
        vec[u] = vec[bigchild];
    }
    else vec[u] = new unordered_map<ll,int>;
    add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 0);
    add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 1);
    for(auto c : v[u])
        if(c.first != p && c.first != bigchild){
            for(auto d : (*vec[c.first]))
                add(*vec[u] , d.second , d.first , h[u] , dep[u] , 1);
            for(auto d : (*vec[c.first]))
                add(*vec[u] , d.second , d.first , h[u] , dep[u] , 0);
        }
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    //freopen(taskname".INP", "r",stdin);
	//freopen(taskname".OUT", "w",stdout);
    cin >> n >> k;
    for(int i = 1 ; i < n ; ++i)
    {
        int a , b , c;cin >> a >> b >> c;
        ++a;++b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    DFS1(1 ,0);
    DSU(1 ,0);
    if(res == maxn)cout << -1;
    else cout << res;
}

Compilation message

/tmp/cc8ukiu6.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccIJuMbL.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccIJuMbL.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status