oj.uz

Submission #645809

# Submission time Handle Problem Language Result Execution time Memory
645809 2022-09-28T03:47:52 Z tamthegod Factories (JOI14_factories) C++14
100 / 100
 5085 ms 212772 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 51628 KB Output is correct
2 Correct 389 ms 62244 KB Output is correct
3 Correct 451 ms 63476 KB Output is correct
4 Correct 441 ms 63340 KB Output is correct
5 Correct 503 ms 63824 KB Output is correct
6 Correct 260 ms 63368 KB Output is correct
7 Correct 434 ms 63484 KB Output is correct
8 Correct 434 ms 63384 KB Output is correct
9 Correct 576 ms 63596 KB Output is correct
10 Correct 247 ms 63512 KB Output is correct
11 Correct 425 ms 63436 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 51412 KB Output is correct
2 Correct 2040 ms 188616 KB Output is correct
3 Correct 2852 ms 190128 KB Output is correct
4 Correct 909 ms 189380 KB Output is correct
5 Correct 3679 ms 212772 KB Output is correct
6 Correct 2906 ms 191488 KB Output is correct
7 Correct 1457 ms 88788 KB Output is correct
8 Correct 503 ms 89448 KB Output is correct
9 Correct 1622 ms 92880 KB Output is correct
10 Correct 1347 ms 89912 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 51628 KB Output is correct
2 Correct 389 ms 62244 KB Output is correct
3 Correct 451 ms 63476 KB Output is correct
4 Correct 441 ms 63340 KB Output is correct
5 Correct 503 ms 63824 KB Output is correct
6 Correct 260 ms 63368 KB Output is correct
7 Correct 434 ms 63484 KB Output is correct
8 Correct 434 ms 63384 KB Output is correct
9 Correct 576 ms 63596 KB Output is correct
10 Correct 247 ms 63512 KB Output is correct
11 Correct 425 ms 63436 KB Output is correct
12 Correct 27 ms 51412 KB Output is correct
13 Correct 2040 ms 188616 KB Output is correct
14 Correct 2852 ms 190128 KB Output is correct
15 Correct 909 ms 189380 KB Output is correct
16 Correct 3679 ms 212772 KB Output is correct
17 Correct 2906 ms 191488 KB Output is correct
18 Correct 1457 ms 88788 KB Output is correct
19 Correct 503 ms 89448 KB Output is correct
20 Correct 1622 ms 92880 KB Output is correct
21 Correct 1347 ms 89912 KB Output is correct
22 Correct 2893 ms 190204 KB Output is correct
23 Correct 2947 ms 192668 KB Output is correct
24 Correct 4129 ms 192208 KB Output is correct
25 Correct 4329 ms 196908 KB Output is correct
26 Correct 4185 ms 193560 KB Output is correct
27 Correct 5085 ms 212268 KB Output is correct
28 Correct 1196 ms 194808 KB Output is correct
29 Correct 4191 ms 193372 KB Output is correct
30 Correct 4257 ms 192952 KB Output is correct
31 Correct 4194 ms 193372 KB Output is correct
32 Correct 1673 ms 95024 KB Output is correct
33 Correct 509 ms 91560 KB Output is correct
34 Correct 1206 ms 88584 KB Output is correct
35 Correct 1251 ms 88572 KB Output is correct
36 Correct 1468 ms 89108 KB Output is correct
37 Correct 1524 ms 89172 KB Output is correct