Submission #767987

#	Time	Username	Problem	Language	Result	Execution time	Memory
767987		phoenix	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KiB

bubblesort2

#include<bits/stdc++.h>
// #include"factories.h"

using namespace std;

struct e {
    int to;
    long long weight;
};

const int dick = 500000 + 5;
vector<e> g[dick];

int nnnn;
int lengthOf[dick];
bool rv[dick];

// first = centroid, second = distance to centroid 
vector<pair<int, long long>> DC[dick];

int count(int s, int p = -1) {
    lengthOf[s] = 1;
    for(auto f : g[s]) {
        if(rv[f.to] || f.to == p) continue;
        lengthOf[s] += count(f.to, s);
    }
    return lengthOf[s];
}

int find_centroid(int s, int p = -1, int mn = nnnn) {
    for(auto f : g[s]) {
        if(rv[f.to] || f.to == p) continue;
        if(lengthOf[f.to] * 2 > mn) return find_centroid(f.to, s, mn);
    }   
    return s;
}
long long dist[dick];
void dfs(int s, int p, int C) {
    DC[s].push_back({C, dist[s]});
    for(auto to : g[s]) {
        if(rv[to.to] || to.to == p) continue;
        dist[to.to] = dist[s] + to.weight;
        dfs(to.to, s, C); 
    }
}
 
void decompose(int s) {
    int C = find_centroid(s, s, count(s));
    dist[C] = 0;
    dfs(C, C, C);

    rv[C] = 1;
    for(auto to : g[C]) {
        if(rv[to.to]) continue;
        decompose(to.to);
    }
}

const long long inf = 1e18;
long long queryDist[dick];
void Init(int N, int A[], int B[], int D[]) {
    nnnn = N;
    for(int i = 0; i < N - 1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    for(int i = 0; i < N; i++)
        queryDist[i] = inf;
    decompose(0);
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < T; i++) {
        int v = Y[i];
        for(auto c : DC[v]) 
            queryDist[c.first] = min(queryDist[c.first], c.second);
    }
    long long res = 1e18;
    for(int i = 0; i < S; i++) {
        int v = X[i];
        for(auto c : DC[v]) 
            res = min(res, c.second + queryDist[c.first]);
    }
    for(int i = 0; i < T; i++) {
        int v = Y[i];
        for(auto c : DC[v]) 
            queryDist[c.first] = inf;
    }
    return res;
}

// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0);cout.tie(0);
//     int n;
//     cin >> n;
//     int a[n - 1], b[n - 1]; long long d[n - 1]; 
//     for(int i = 0; i < n - 1; i++) {
//         cin >> a[i];
//         cin >> b[i];
//         cin >> d[i];
//     }
//     Init(n, a, b, d);
//     int t;
//     cin >> t;
//     while(t--) {
//         int s, t;
//         cin >> s;
//         int x[s]; 
//         for(int i = 0; i < s; i++)
//             cin >> x[i];
//         cin >> t; 
//         int y[t];
//         for(int i = 0; i < t; i++)
//             cin >> y[i];
//         cout << Query(s, x, t, y) << '\n';
//     }    
// }

Compilation message (stderr)

/usr/bin/ld: /tmp/cckuZ72K.o: in function `main':
grader.cpp:(.text.startup+0x181): undefined reference to `countScans(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status