Submission #656566

#	Time	Username	Problem	Language	Result	Execution time	Memory
656566		minhcool	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KiB

factories

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;

ll n;
vector<pair<ll, ll>> Adj[N];

ll d1[N], d2[N];

ll anc[N][20];
//dist[N][20];

void dfs(int u, int p){
    for(auto it : Adj[u]){
        int v = it.fi, w = it.se;
        if(v == p) continue;
        d1[v] = d1[u] + 1;
        d2[v] = d2[u] + w;
        anc[v][0] = u;
        //dist[v][0] = w;
        dfs(v, u);
    }
}

void prep(){
    for(int i = 1; i <= 19; i++){
        for(int j = 1; j <= n; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            //dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
        }
    }
}

int lca(int x, int y){
    if(d1[x] > d1[y]) swap(x, y);
    for(int i = 19; i >= 0; i--){
        if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i], y = anc[y][i];
        }
    }
    return anc[x][0];
}

ll dist(int x, int y){
    return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}

void Init(int N, vector<int> A, vector<int> B, vector<int> D){
    n = N;
    for(int i = 0; i < (n - 1); i++){
        Adj[A[i] + 1].pb({B[i] + 1, D[i]});
        Adj[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    dfs(1, 1);
    prep();
}

ll Query(int S, vector<int> X, int T, vector<int> Y){
    if(S <= 5000 && T <= 5000){
        ll ans = oo;
        for(int i = 0; i < X.size(); i++){
            for(int j = 0; j < Y.size(); j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
        }
        return ans;
    }
}

void process(){
    int n, q;
    vector<int> a(n - 1), b(n - 1), d(n - 1);
    cin >> n >> q;
    for(int i = 0; i < (n - 1); i++){
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    while(q--){
        int sz1, sz2;
        vector<int> vc1, vc2;
        cin >> sz1 >> sz2;
        vc1.resize(sz1);
        for(int i = 0; i < sz1; i++) cin >> vc1[i];
        vc2.resize(sz2);
        for(int i = 0; i < sz2; i++) cin >> vc2[i];
        cout << Query(sz1, vc1, sz2, vc2) << "\n"; 
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    process();
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, std::vector<int>, int, std::vector<int>)':
factories.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i = 0; i < X.size(); i++){
      |                        ~~^~~~~~~~~~
factories.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int j = 0; j < Y.size(); j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
      |                            ~~^~~~~~~~~~
factories.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^
factories.cpp: In function 'void process()':
factories.cpp:84:21: warning: 'n' is used uninitialized in this function [-Wuninitialized]
   84 |     vector<int> a(n - 1), b(n - 1), d(n - 1);
      |                   ~~^~~
/usr/bin/ld: /tmp/cc257pWm.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuiN9bq.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc257pWm.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status