Submission #553670

#	Time	Username	Problem	Language	Result	Execution time	Memory
553670		LucaDantas	Factories (JOI14_factories)	C++17	0 / 100	38 ms	48512 KiB

factories

// Recodando pra lembrar virtual tree
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 5e5+10, logn = 21;
constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

vector<pair<int,long long>> g[maxn];

int in[maxn], pai[logn][maxn], profundidade[maxn], t, n;
long long depth[maxn];

void dfs(int u) {
    in[u] = ++t;
    for(auto [v, w] : g[u]) {
        if(v == pai[u][0]) continue;
        pai[v][0] = u;
        profundidade[v] = profundidade[u] + 1;
        depth[v] = depth[u] + w;
        dfs(v);
    }
}

void build_binary_lifting() {
    for(int l = 1; l < logn; l++)
        for(int i = 1; i <= n; i++)
            pai[i][l] = pai[pai[i][l-1]][l-1];
}

int LCA(int a, int b) {
    if(profundidade[a] < profundidade[b])
        swap(a, b);
    for(int l = logn-1; l >= 0; l--)
        if(profundidade[a] - (1<<l) >= profundidade[b])
            a = pai[a][l];
    if(a == b) return a;
    for(int l = logn-1; l >= 0; l--)
        if(pai[a][l] != pai[b][l])
            a = pai[a][l], b = pai[b][l];
    return pai[a][0];
}

vector<pair<int, long long>> vt[maxn];

void get_vt(vector<int>& v) {
    	sort(v.begin(), v.end(), [](int a, int b) { return in[a] < in[b]; });
	
	int tam = v.size();
	for(int i = 1; i < tam; i++)
		v.push_back(LCA(v[i-1], v[i]));
 
	sort(v.begin(), v.end(), [](int a, int b) { return in[a] < in[b]; });
	v.erase(unique(v.begin(), v.end()), v.end());
	
	for(int x : v)
		vt[x].clear();
 
	for(int i = 1; i < v.size(); i++) {
		int lca = LCA(v[i-1], v[i]);
		long long DIST = depth[v[i]] - depth[lca];
		vt[lca].push_back({v[i], DIST});
		vt[v[i]].push_back({lca, DIST});
	}
    // sort(v.begin(), v.end(), [](const int& a, const int& b) { return in[a] < in[b]; });
    // int sz = (int)v.size();
    // for(int i = 1; i < sz; i++)
    //     v.push_back(LCA(v[i], v[i-1]));
    // sort(v.begin(), v.end(), [](const int& a, const int& b) { return in[a] < in[b]; });
    // v.erase(unique(v.begin(), v.end()), v.end());
    // for(int x : v)
    //     vt[x].clear();
    // for(int i = 1; i < (int)(v.size()); i++) {
    //     int lca = LCA(v[i], v[i-1]);
    //     long long d = depth[v[i]] - depth[lca];
    //     vt[v[i]].push_back({lca, d});
    //     vt[lca].push_back({v[i], d});
    // }
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    n = N;
    for(int i = 0; i < n-1; i++) {
        A[i]++, B[i]++;
        g[A[i]].push_back({B[i], D[i]}), g[B[i]].push_back({A[i], D[i]});
    }
    profundidade[1] = 1;
    depth[1] = 1;
    dfs(1);
    build_binary_lifting();
}

long long dd[maxn];
bool mark[maxn];

long long dijkstra(const vector<int>& tudo, const vector<int>& X, const vector<int>& Y) {
    static priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> q;
    for(int x : tudo)
        dd[x] = inf, mark[x] = 0;
    for(int x : Y)
        dd[x] = 0, q.push({0, x});

    while(q.size()) {
        int u = q.top().second;
        q.pop();
        if(mark[u]) continue;
        mark[u] = 1;

        for(auto [v, w] : vt[u])
            if(dd[v] > dd[u] + w)
                dd[v] = dd[u] + w, q.push({dd[v], v});
    }

    long long ans = inf;
    for(int x : X)
        ans = min(ans, dd[x]);
    return ans;
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    vector<int> v, x, y;
    for(int i = 0; i < S; i++)
        v.push_back(X[i]+1), x.push_back(X[i]+1);
    for(int i = 0; i < T; i++)
        v.push_back(Y[i]+1), y.push_back(Y[i]+1);
    get_vt(v);
    return dijkstra(v, x, y);
}

Compilation message (stderr)

factories.cpp: In function 'void get_vt(std::vector<int>&)':
factories.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 1; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~

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