Submission #645809

#	Time	Username	Problem	Language	Result	Execution time	Memory
645809		tamthegod	Factories (JOI14_factories)	C++14	100 / 100	5085 ms	212772 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
vector<pair<int, int>> adj[maxN];
int n, q;
vector<int> tour;
int pos[maxN];
int rmq[maxN][21];
int lg[maxN];
int depth[maxN];
vector<int> vc[maxN];
ll f[maxN];
ll F[maxN];
ll dp[maxN];
int vis[maxN];
int parCent[maxN];
void Log()
{
    for(int i=2; i<maxN; i++)
        lg[i] = lg[i / 2] + 1;
}
void predfs(int u, int par)
{
    pos[u] = tour.size();
    tour.pb(u);
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        f[v] = f[u] + w;
        predfs(v, u);
        tour.pb(u);
    }
}
int mini(int u, int v)
{
    return depth[u] < depth[v] ? u : v;
}
int LCA(int u, int v)
{
    int l = min(pos[u], pos[v]), r = max(pos[u], pos[v]);
    int k = lg[r - l + 1];
    return mini(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
ll dist(int u, int v)
{
    return f[u] + f[v] - 2 * f[LCA(u, v)];
}
int dfs(int u, int par)
{
    dp[u] = 1;
    for(auto a : adj[u])
    {
        int v = a.fi;
        if(v == par || vis[v])
            continue;
        dp[u] += dfs(v, u);
    }
    return dp[u];
}
int Find_Centroid(int u, int par, int sz)
{
    for(auto a : adj[u])
    {
        int v = a.fi;
        if(v == par || vis[v])
            continue;
        if(dp[v] > sz / 2)
            return Find_Centroid(v, u, sz);
    }
    return u;
}
int Decompose(int u)
{
    int root = Find_Centroid(u, 0, dfs(u, 0));
    vis[root] = 1;
    for(auto a : adj[root])
    {
        int v = a.fi;
        if(vis[v])
            continue;
        parCent[Decompose(v)] = root;
    }
    return root;
}
void update(int u)
{
    for(int v=u; v; v=parCent[v])
    {
        F[v] = min(F[v], dist(u, v));
    }
}
void del(int u)
{
    for(int v=u; v; v=parCent[v])
    {
        F[v] = oo;
    }
}
ll get(int u)
{
    ll res = oo;
    for(int v=u; v; v=parCent[v]) res = min(res, F[v] + dist(u, v));
    return res;
}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i=0; i<n-1; i++)
    {
        int u = A[i] + 1, v = B[i] + 1, w = D[i];
       // cout << u << " " << v << " " << w << '\n';
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    Log();
    depth[1] = 1;
    tour.clear();
    //cout << Decompose(1);return;
    predfs(Decompose(1), 0);
    for (int i = 0; i < tour.size(); i++)
    {
        rmq[i][0] = tour[i];
    }

    for (int i = 1; i <=20; i++)
    {
        for (int j = 0; j < tour.size(); j++)
        {
            if (j + (1 << (i - 1)) >= tour.size())
                rmq[j][i] = rmq[j][i - 1];
            else
                rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
        }
    }
   // cout << LCA(4, 7);return;
    fill(F, F + n + 1, oo);
    //cout << dist(4, 7);return;
}
long long Query(int S, int X[], int T, int Y[])
{
    for(int i=0; i<S; i++)
    {
        int u = X[i] + 1;
        update(u);
    }
    ll res = oo;
    for(int i=0; i<T; i++)
    {
        int u = Y[i] + 1;
        res = min(res, get(u));
    }
    for(int i=0; i<S; i++)
    {
        int u = X[i] + 1;
        del(u);
    }
    return res;
}
void ReadInput()
{
    cin >> n >> q;
    for(int i=1; i<n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++;
        v++;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
}
void Solve()
{
    Log();
    depth[1] = 1;
    tour.clear();
    //cout << Decompose(1);return;
    predfs(Decompose(1), 0);
    for (int i = 0; i < tour.size(); i++)
    {
        rmq[i][0] = tour[i];
    }

    for (int i = 1; i <=20; i++)
    {
        for (int j = 0; j < tour.size(); j++)
        {
            if (j + (1 << (i - 1)) >= tour.size())
                rmq[j][i] = rmq[j][i - 1];
            else
                rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
        }
    }
   // cout << LCA(4, 7);return;
    fill(F, F + n + 1, oo);
    //cout << dist(4, 7);return;
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        vector<int> vc;
        for(int i=1; i<=x; i++)
        {
            int u;
            cin >> u;
            u++;
            update(u);
            vc.pb(u);
        }
        ll res = oo;
        for(int i=1; i<=y; i++)
        {
            int v;
            cin >> v;
            v++;
            res = min(res, get(v));
        }
        for(int u : vc) del(u);
        cout << res << '\n';
    }
}
/*int32_t main()
{
    freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}*/

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < tour.size(); i++)
      |                     ~~^~~~~~~~~~~~~
factories.cpp:139:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (int j = 0; j < tour.size(); j++)
      |                         ~~^~~~~~~~~~~~~
factories.cpp:141:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             if (j + (1 << (i - 1)) >= tour.size())
      |                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: In function 'void Solve()':
factories.cpp:191:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |     for (int i = 0; i < tour.size(); i++)
      |                     ~~^~~~~~~~~~~~~
factories.cpp:198:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         for (int j = 0; j < tour.size(); j++)
      |                         ~~^~~~~~~~~~~~~
factories.cpp:200:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |             if (j + (1 << (i - 1)) >= tour.size())
      |                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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