Submission #1219907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219907		sano	Factories (JOI14_factories)	C++20	100 / 100	2486 ms	342160 KiB

factories

#include "factories.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

vec<vec<pii>> g;
vec<vec<pii>> pred;
vec<bool> je;
vec<ll> podst;
vec<ll> hod;

void vpodst(ll x, ll pr = -1) {
    podst[x] = 1;
    for (auto &i : g[x]) {
        if (i.ff == pr || je[i.ff]) continue;
        vpodst(i.ff, x);
        podst[x] += podst[i.ff];
    }
    return;
}

ll centroid(ll x, ll vel, ll pr = -1) {
    for (auto &i : g[x]) {
        if (je[i.ff] || i.ff == pr) continue;
        if (podst[i.ff] * 2 > vel) {
            return centroid(i.ff, vel, x);
        }
    }
    return x;
}

void pocitaj_pred(ll x, ll c, ll pr = -1, ll dist = -1) {
    pred[x].push_back({ c, dist });
    for (auto i : g[x]) {
        if (je[i.ff] || i.ff == pr) continue;
        pocitaj_pred(i.ff, c, x, dist + i.ss);
    }
    return;
}

void build_centroid(ll x = 0) {
    vpodst(x);
    ll c = centroid(x, podst[x]);
    je[c] = 1;
    for (auto &i : g[c]) {
        if (je[i.ff]) continue;
        pocitaj_pred(i.ff, c, c, i.ss);
        build_centroid(i.ff);
    }
    return;
}

void Init(int n2, int a2[], int b2[], int d2[]) {
    ll n = n2;
    vec<ll> a, b, d;
    For(i, n - 1) {
        a.push_back(a2[i]);
        b.push_back(b2[i]);
        d.push_back(d2[i]);
    }
    g.resize(n);
    hod.resize(n, NEK);
    podst.resize(n, 1);
    For(i, n-1) {
        g[a[i]].push_back({ b[i], d[i] });
        g[b[i]].push_back({ a[i], d[i] });
    }
    pred.resize(n);
    je.resize(n, 0);
    build_centroid();
}

ll Query(int s2, int x2[], int t2, int y2[]) {
    ll s = s2, t = t2;
    vec<ll> x, y;
    For(i, s) x.push_back(x2[i]);
    For(i, t) y.push_back(y2[i]);
    For(i, s) {
        hod[x[i]] = 0;
        for (auto &j : pred[x[i]]) {
            hod[j.ff] = min(hod[j.ff], j.ss);
        }
    }
    ll mini = NEK;
    For(i, t) {
        mini = min(mini, hod[y[i]]);
        for (auto& j : pred[y[i]]) {
            mini = min(mini, hod[j.ff] + j.ss);
        }
    }
    For(i, s) {
        hod[x[i]] = NEK;
        for (auto& j : pred[x[i]]) {
            hod[j.ff] = NEK;
        }
    }
    return mini;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    int q; cin >> q;
    int a[100], b[100], d[100];
    For(i, n - 1) {
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    For(i, q) {
        int s, t; cin >> s >> t;
        int x[100], y[100];
        For(j, s) {
            cin >> x[j];
        }
        For(j, t) {
            cin >> y[j];
        }
        cout << Query(s, x, t, y) << '\n';
    }

    return 0;
}*/

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