Submission #1219896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219896		sano	공장들 (JOI14_factories)	C++20	0 / 100	4 ms	580 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(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000
#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;

const int M = 21;

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

void vpodst(int x, int 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;
}

int centroid(int x, int vel, int 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(int x, int c, int pr = -1, int 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(int x = 0) {
    vpodst(x);
    int 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 n, int a[], int b[], int d[]) {
    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 s, int x[], int t, int y[]) {
    For(i, s) {
        hod[x[i]] = 0;
        for (auto &j : pred[x[i]]) {
            hod[j.ff] = min(hod[j.ff], j.ss);
        }
    }
    int mini = NEK;
    For(i, t) {
        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;
    vec<int> a(n), b(n), d(n);
    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;
        vec<int> x(s), y(t);
        For(j, s) {
            cin >> x[j];
        }
        For(j, t) {
            cin >> y[j];
        }
        cout << Query(s, x, t, y) << '\n';
    }

    return 0;
}*/

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