Submission #945214

#	Time	Username	Problem	Language	Result	Execution time	Memory
945214		VMaksimoski008	Factories (JOI14_factories)	C++14	15 / 100	7749 ms	524288 KiB

factories

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

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int maxn = 5e5 + 5;

int n, del[maxn], sub[maxn];
ll dist[maxn];
vector<vector<pll> > graph(maxn), anc(maxn);

int get_sub(int u, int p) {
    for(auto &[v, _] : graph[u])
        if(v != p && !del[v]) sub[u] += get_sub(v, u);
    return ++sub[u];
}

int get_cen(int u, int p, int sz) {
    for(auto &[v, _] : graph[u])
        if(v != p && !del[v] && 2 * sub[v] > sz) return get_cen(v, u, sz);
    return u;
}

void get_dist(int u, int cen, int p, ll d) {
    for(auto &[v, w] : graph[u])
        if(v != p && !del[v]) get_dist(v, cen, u, d + w);
    anc[u].push_back({ cen, d });
}

void update(int u, int t) {
    for(auto &[v, d] : anc[u])
        dist[v] = (t ? min(dist[v], d) : 1e18);
    dist[u] = (t ? 0 : 1e18);
}

ll query(int u) {
    ll ans = dist[u];
    for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
    return ans;
}

void build(int u) {
    int cen = get_cen(u, -1, get_sub(u, -1));

    for(auto &[v, w] : graph[cen])
        if(!del[v]) get_dist(v, cen, cen, w);

    del[cen] = 1;
    for(auto &[v, w] : graph[cen])
        if(!del[v]) build(v);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<n-1; i++) {
        graph[A[i]].push_back({ B[i], D[i] });
        graph[B[i]].push_back({ A[i], D[i] });
    }
    for(int i=0; i<n; i++) dist[i] = 1e18;
    build(0);
}

ll Query(int S, int X[], int T, int Y[]) {
    ll ans = 1e18;
    for(int i=0; i<S; i++) update(X[i], 1);
    for(int i=0; i<T; i++) ans = min(ans, query(Y[i]));
    for(int i=0; i<S; i++) update(X[i], 0);
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:15:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto &[v, _] : graph[u])
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto &[v, _] : graph[u])
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto &[v, w] : graph[u])
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto &[v, d] : anc[u])
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto &[v, w] : graph[cen])
      |               ^
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto &[v, w] : graph[cen])
      |               ^

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