제출 #689823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689823		vjudge1	공장들 (JOI14_factories)	C++17	100 / 100	4570 ms	254520 KiB

factories

#define taskname "Factories"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 5e5 + 10;
vector<ii> adj[maxn];
vector<int> dis[maxn];
int sz[maxn], pa[maxn], dp[maxn], ban[maxn], n, q;

void DFSz(int u, int p = -1)
{
    sz[u] = 1;
    for (auto [v, c]: adj[u]) if (v != p && !ban[v]) DFSz(v, u), sz[u] += sz[v];
}

int getcen(int u, int need, int p = -1)
{
    if (sz[u] <= need) return p;
    ii big = {0, 0};
    for (auto [v, c]: adj[u]) if (v != p && !ban[v]) big = max(big, {sz[v], v});
    return getcen(big.ss, need, u);
}

void DFS(int u, int des, int p, int dep)
{
    dis[u].emplace_back(dep);
    for (auto [v, c]: adj[u]) if (v != p && !ban[v]) DFS(v, des, u, dep+c);
}

void build(int u = 1, int p = 0)
{
    DFSz(u);
    u = getcen(u, sz[u]/2);
    pa[u] = p;
//    cerr<<"TREE: "<<p-1<<" "<<u-1<<"\n";
    ban[u] = 1;
    dp[u] = 1e18;
    dis[u].emplace_back(0);
    for (auto [v, c]: adj[u]) if (!ban[v])
    {
        DFS(v, u, u, c);
        build(v, u);
    }
}

inline void upd(int pos)
{
    int u = pos;
    for (int i=(int)dis[u].size()-1; i>=0; i--)
    {
        int j = dis[u][i];
//        cerr<<i<<" "<<j<<"\n";
        dp[pos] = min(dp[pos], j);
        pos = pa[pos];
    }
}

inline int qry(int pos)
{
    int u = pos;
    int ans = 1e18;
    for (int i=(int)dis[u].size()-1; i>=0; i--)
    {
        int j = dis[u][i];
        ans = min(ans, dp[pos] + j);
        pos = pa[pos];
    }
    return ans;
}

inline void rollback(int pos) {
    int u = pos;
    for (int i=(int)dis[u].size()-1; i>=0; i--)
    {
        int j = dis[u][i];
//        cerr<<i<<" "<<j<<"\n";
        dp[pos] = 1e18;
        pos = pa[pos];
    }
}

void Init(int32_t N, int32_t a[], int32_t b[], int32_t d[])
{
    for (int i=0; i<=N-2; i++)
    {
        int u = a[i]+1, v = b[i]+1, c = d[i];
//        cerr<<u<<" "<<v<<" "<<c<<"\n";
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }
    build();
//    for (int i=1; i<=N; i++) cerr<<"WEIRD: "<<i<<" "<<dis[i].size()<<"\n";
}

int Query(int32_t s, int32_t x[], int32_t t, int32_t y[])
{
//    if (s > t)
//    {
//        swap(s, t);
//        swap(x, y);
//    }
    for (int i=0; i<s; i++) upd(x[i]+1);
    int ans = 1e18;
    for (int i=0; i<t; i++) ans = min(ans, qry(y[i]+1));
    for (int i=0; i<s; i++) rollback(x[i]+1);
    return ans;
}


//signed main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr); cout.tie(nullptr);
//    int32_t a[] = {0, 1, 2, 2, 4, 1}, b[] = {1, 2, 3, 4, 5, 6}, d[] = {4, 4, 5, 6, 5, 3};
//    Init(7, a, b, d);
//    {
//        int32_t q1[] = {0, 6}, q2[] = {3, 4};
//        cout<<Query(2, q1, 2, q2)<<"\n"; //returns 12.
//    }
//    {
//        int32_t q1[] = {0, 1, 3}, q2[] = {4, 6};
//        cout<<Query(3, q1, 2, q2)<<"\n"; //returns 3.
//    }
//    {
//        int32_t q1[] = {2}, q2[] = {5};
//        cout<<Query(1, q1, 1, q2)<<"\n"; //returns 11.
//    }
//}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void rollback(long long int)':
factories.cpp:79:13: warning: unused variable 'j' [-Wunused-variable]
   79 |         int j = dis[u][i];
      |             ^

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