Submission #482899

#	Time	Username	Problem	Language	Result	Execution time	Memory
482899		Karliver	Factories (JOI14_factories)	C++17	100 / 100	4723 ms	365052 KiB

factories

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

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int MX = 5e5 + 100;
const ll inf = (ll)1e18;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}

bool R[MX];

int S[MX], N;

struct info {
    int v;
    ll d;
};
V<info> nd[MX];
V<PR<int>> cd(MX);
V<PR<int>> g[MX];
V<ll> mi(MX);

int dfs_sz(int v, int p = -1) {
    S[v] = 1;
    for(auto [c, w] : g[v]) {
        if(c == p || R[c])continue;
        S[v] += dfs_sz(c, v);
    }
    return S[v];
}

int get_cen(int v, int ms, int p = -1) {
    for(auto [c, w] : g[v])
        if(c != p && !R[c] && S[c] * 2 > ms)
            return get_cen(c, ms, v);
    
    return v;
}

void dfs1(int v, int p, int tp, ll d = 0) {
    nd[v].push_back({tp, d});
    for(auto [c, w] : g[v]) {
        if(c != p && !R[c]) {
            
            dfs1(c, v, tp, d + w);

        }
    }
    
}

void cen(int v = 1) {
    v = get_cen(v, dfs_sz(v));

    R[v] = 1;
    
    dfs1(v, v, v);

    for(auto [c, w] : g[v]) {
        if(!R[c])
            cen(c);
    }

}

void Init(int N, int *a, int *b, int *c) {
    
    forn(i, N - 1) {
        ++a[i], ++b[i];
        g[a[i]].push_back({b[i], c[i]});
        g[b[i]].push_back({a[i], c[i]});
    }
    for(int i = 1;i <= N;++i) mi[i] = inf;
    cen();
}

long long Query(int S, int *a, int T, int *b) {
    forn(i, S) a[i]++;
    forn(i, T) b[i]++;

    V<int> del;
    forn(i, S) {
        int x = a[i];
        for(auto p : nd[x]) {
            ckmi(mi[p.v], p.d);
            del.push_back(p.v);
        }
    }
    ll ret = inf;
    forn(i, T) {
        int x = b[i];
        for(auto p : nd[x]) {
            ckmi(ret, mi[p.v] + p.d);    
        }
    }
    for(auto c : del) mi[c] = inf;
    assert(ret != inf);
    return ret;
}

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