제출 #993724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993724		gortomi	공장들 (JOI14_factories)	C++17	0 / 100	2384 ms	299284 KiB

factories

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

//#include "grader.cpp"
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
vector<vector<pii> > g;
vector<bool> vis;
vector<long long> s;
vector<vector<ll> > d;
vector<vector<long long> > pa;
vector<ll> mini;
void calc(long long v, long long p)
{
    s[v] = 1;
    for(auto [x, w] : g[v])
    {
        if(vis[x]) continue;
        if(x == p) continue;
        calc(x, v);
        s[v] += s[x];
    }
}
long long findc(long long v, long long p, long long bp)
{

    for(auto [x, w] : g[v])
    {
        if(x == p || vis[x]) continue;
        if(s[bp] / 2 < s[x]) return findc(x, v, bp);
    }
    return v;
}
void calc2(long long v, long long p, ll dep, long long l, long long bp)
{
    pa[v][l] = bp;
    d[v][l] = dep;
    for(auto [x, w] : g[v])
    {
        if(x == p || vis[x]) continue;
        calc2(x, v, dep + w, l, bp);
    }
}
void dec(long long v, long long l)
{

    calc(v, 0);
    long long c = findc(v, 0, v);
    vis[c] = 1;
    calc2(c, 0, 0, l, c);

    for(auto [x, w] : g[c])
    {

        if(!vis[x]) dec(x, l + 1);

    }
}
ll Query(int t, int b[], int s, int a[])
{
    vector<long long> ve;
    for(long long i = 0; i < s; i++)
    {
        long long x = a[i];
        for(long long j = 0; j < 20; j++)
        {
            long long v = pa[x][j];
            if(v != 0)
            {
                mini[v] = min(mini[v], d[x][j]);
                ve.push_back(v);
            }
        }
    }
    ll ans = 1e15;
    for(long long i = 0; i < t; i++)
    {
        long long x = b[i];
        ll act = 1e15;
        for(long long j = 0; j < 20; j++)
        {
            long long v = pa[x][j];
            if(v != 0)
            {
                act = min(act, mini[v] + d[x][j]);
            }
        }
        ans = min(act, ans);
    }
    for(auto x : ve) mini[x] = 1e15;
    return ans;
}
void Init(int n, int a[], int b[], int c[])
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    /*int n, q;
    cin >> n >> q;*/
    g.resize(n);
    vis.resize(n);
    s.resize(n);
    d.resize(n, vector<ll>(20));
    pa.resize(n, vector<long long>(20));
    mini.resize(n, 1e15);
    for(long long i = 0; i < n - 1; i++)
    {
        ll x = a[i], y = b[i], w = c[i];
        /*int x, y, w;
        cin >> x >> y >> w;*/
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    dec(1, 0);
    /*while(q--)
    {
        int s, t;
        cin >> s >> t;
        int a[s], b[t];
        for(int i = 0; i < s; i++) cin >> a[i];
        for(int i = 0; i < t; i++) cin >> b[i];
        cout << Query(s, a, t, b) << "\n";
    }*/
}

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