Submission #482842

#	Time	Username	Problem	Language	Result	Execution time	Memory
482842		Karliver	Factories (JOI14_factories)	C++17	0 / 100	52 ms	80196 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)1e16;
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];
ll d, ret = inf;
int tp, b, S[MX], N, Q;

struct info {
    int v, tp;
    ll d;
};
V<info> nd[MX];
struct cen_info {
    pair<ll, int> h1{inf, -1}, h2{inf, -1};
};
V<cen_info> cd(MX);
V<PR<int>> g[MX];
bool is[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) {

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

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

    R[v] = 1;

    for(auto [c, w] : g[v]) {
        if(!R[c]) {
            b = v;
            tp = c;
            d = w;
            dfs1(c, v);
        }
    }


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

}

void Init(int _N, int a[], int b[], int c[]) {
    N = _N;
    forn(i, N - 1) {
        
        g[a[i]].push_back({b[i], c[i]});
        g[b[i]].push_back({a[i], c[i]});
    }
    cen();
}

long long Query(int A, int a[], int B, int b[]) {
   
    forn(i, A) {
        int x = a[i];
        is[x] = 1;
        for(auto p : nd[x]) {
            auto &f = cd[p.v].h1;
            auto &s = cd[p.v].h2;
            if(p.d < f.first) {
                if(f.second != p.tp)swap(f, s);
                f = {p.d, p.tp};
            }
            else if(p.d < s.first) {
                if(p.tp != f.second)
                    s = {p.d, p.tp};
            }
        }
    }
    ret = inf;
    forn(i, B) {
        int x = b[i];
        if(is[x])ret = 0;
        for(auto p : nd[x]) {
            auto &f = cd[p.v].h1;
            auto &s = cd[p.v].h2;
            if(is[p.v])ckmi(ret, p.d);
            if(p.tp == f.second) {
                ckmi(ret, p.d + s.first);
            }
            else ckmi(ret, p.d + f.first);
            ckmi(ret, cd[x].h1.first);

        }
    }
    forn(i, A) {
        int x= a[i];
        is[x] = 0;
        for(auto  p : nd[x]) {
            cd[p.v].h1 = cd[p.v].h2 = {inf, -1};
        }
    }
    assert(ret != inf);
    return ret;
}

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