Submission #945221

#	Time	Username	Problem	Language	Result	Execution time	Memory
945221		VMaksimoski008	Factories (JOI14_factories)	C++14	100 / 100	3907 ms	341332 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
using ll = long long;
 
const int maxn = 5e5 + 5;
 
ll n, del[maxn], sub[maxn], dist[maxn];
vector<vector<pair<ll, ll> > > G(maxn), anc(maxn);
 
int get_sub(int u, int p) {
    sub[u] = 1;
    for(auto &[v, _] : G[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, _] : G[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] : G[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]) {
        if(t) dist[v] = min(dist[v], d);
        else dist[v] = 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] : G[cen])
        if(!del[v]) get_dist(v, cen, cen, w);
 
    del[cen] = 1;
    for(auto &[v, w] : G[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++) {
        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++) 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:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto &[v, _] : G[u])
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto &[v, _] : G[u])
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto &[v, w] : G[u])
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:32:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto &[v, d] : anc[u]) {
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto &[v, w] : G[cen])
      |               ^
factories.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto &[v, w] : G[cen])
      |               ^

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