Submission #780084

#	Time	Username	Problem	Language	Result	Execution time	Memory
780084		adaawf	Factories (JOI14_factories)	C++14	18 / 100	8044 ms	126888 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long int f[500005];
int n, d[500005];
vector<int> gg[500005], g[500005];
int p[500005][25];
void bfs(int x) {
    queue<int> q;
    q.push(x);
    p[x][0] = x;
    f[x] = d[x] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int j = 1; j <= 19; j++) {
             p[u][j] = p[p[u][j - 1]][j - 1];
             if (p[u][j] == 0) break;
        }
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (d[u] + 1 < d[v]) {
                d[v] = d[u] + 1;
                f[v] = f[u] + gg[u][i];
                p[v][0] = u;
                q.push(v);
            }
        }
    }
}
int lca(int u, int v) {
    if (d[u] > d[v]) {
        swap(u, v);
    }
    for (int j = 19; j >= 0; j--) {
        if (d[p[v][j]] >= d[u]) {
            v = p[v][j];
        }
    }
    if (u == v) return u;
    for (int j = 19; j >= 0; j--) {
        if (p[u][j] != p[v][j]) {
            u = p[u][j];
            v = p[v][j];
        }
    }
    return p[v][0];
}
long long int check(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < 500005; i++) {
        f[i] = 999999999999999999;
        d[i] = n * 2;
    }
    for (int i = 0; i < n - 1; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(v);
        g[v].push_back(u);
        gg[u].push_back(w);
        gg[v].push_back(w);
    }
    bfs(0);
}
long long int Query(int S, int X[], int T, int Y[]) {
    if (S > 20 && T > 20) {
        vector<long long int> ff(n);
        vector<bool> dda(n), dd(n);
        for (int i = 0; i < T; i++) {
            dda[Y[i]] = 1;
        }
        for (int i = 0; i <= n; i++) {
            dd[i] = dda[i] = 0;
            ff[i] = 999999999999999999;
        }
        priority_queue<pair<long long int, long long int>>q;
        for (int i = 0; i < S; i++) {
            q.push({0, X[i]});
            ff[X[i]] = 0;
        }
        while (!q.empty()) {
            int u = q.top().second;
            q.pop();
            if (dd[u] == 1) continue;
            dd[u] = 1;
            if (dda[u] == 1) return ff[u];
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u][i], w = gg[u][i];
                if (ff[u] + w < ff[v]) {
                    ff[v] = ff[u] + w;
                    q.push({-ff[v], v});
                }
            }
        }
    }
    long long int res = 999999999999999999;
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < T; j++) {
            res = min(res, check(X[i], Y[j]));
        }
    }
    return res;
}

Compilation message (stderr)

factories.cpp: In function 'void bfs(int)':
factories.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < g[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:89:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for (int i = 0; i < g[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67