Submission #1000622

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000622	2024-06-18T04:44:14 Z	nmts	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout)
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define pdd pair < double , double >
#define fi first
#define se second
#define mii map< int , int>
#define mdd map< double , double >
#define qi queue < int >
#define dqi deque< int >
#define pf(x) push_front(x)
#define popf pop_front()
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i) 
#define mask(i) ((1LL << (i)))  
#define status(x, i) (((x) >> (i)) & 1)  
#define set_on(x, i) ((x) | mask(i)) 
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'    
#define int long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const int INF= 1e9;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

int n , k;

vector<pii> edges[maxn];

int val[maxn];
int hight[maxn];
int parent[maxn][LOG+1];

void dfs(int u , int p)
{

    for (pii v : edges[u])
        if (v.fi != p)
            {
                parent[v.fi][0] = u;
                hight[v.fi] = hight[u] + 1;
                val[v.fi] = val[u] + v.se;
                dfs(v.fi , u );
            }

}

void prepare()
{
    dfs(1 , 0);
    hight[0] = -1;

    for (int j=1 ; j<=LOG ; ++j)
        for (int i=1 ; i<=n ; ++i)
            parent[i][j] = parent[parent[i][j-1]][j-1];

}

int lca(int u , int v)
{

    if (hight[u] < hight[v]) return lca(v , u);

    for (int i=LOG ; i>=0 ; --i) 
        if (hight[parent[u][i]] >= hight[v]) u = parent[u][i];

    if (u == v) return u;

    for (int i=LOG ; i>=1 ; --i)
        if (parent[u][i] != parent[v][i]) u = parent[u][i] , v = parent[v][i];

    return parent[v][0];
    

}

int best_path(int n , int k , int adj[][2] , int weights[])
{

    if (k == 1) return 0;

    for (int i=0 ; i<n-1 ; ++i)
        {
            int u , v , w ; 
            u = adj[i][0];
            v = adj[i][1];
            w = weights[i];
            ++u , ++v;
            edges[u].push_back({v , w});
            edges[v].push_back({u , w});
        }
    prepare();

    int ans = INF;

    for (int i=2 ; i<=n ; ++i)
        for (int j=1 ; j<i ; ++j)
            {
                int l = lca(i , j);

                if (val[i] + val[j] - 2*val[l] == k) 
                    minimize(ans , hight[i] + hight[j] - 2 * hight[l]);

            }


    return ans;
    
}   

Compilation message

/usr/bin/ld: /tmp/cc6CgaFZ.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