Submission #570726

#	Time	Username	Problem	Language	Result	Execution time	Memory
570726		YouAreMyGalaxy	Factories (JOI14_factories)	C++17	100 / 100	5920 ms	194196 KiB

factories

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include "factories.h"
 
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 5e5, cbit = 19;
const long long oo = 1e18;
vector<pair<int, int> > Adj[N + 1];
long long dp[N + 1], sum[N + 1];
int f[2 * N + 1][cbit + 1], par[N + 1], sz[N + 1], depth[N + 1], timer, logg[2 * N + 1], pos[N + 1];
bool visited[N + 1];
void DFS(int u, int p)
{
    f[++timer][0] = u;
    logg[timer] = logg[timer >> 1] + 1;
    pos[u] = timer;
    dp[u] = oo;
    for (auto x : Adj[u])
    {
        int v = x.first, w = x.second;
        if (v == p)
        {
            continue;
        }
        f[++timer][0] = u;
        logg[timer] = logg[timer >> 1] + 1;
        depth[v] = depth[u] + 1;
        sum[v] = sum[u] + w;
        DFS(v, u);
    }
}
int LCA(int u, int v)
{
    if (pos[u] > pos[v])
    {
        swap(u, v);
    }
    int k = logg[pos[v] - pos[u] + 1];
    u = f[pos[u]][k];
    v = f[pos[v] - (1 << k) + 1][k];
    if (depth[u] < depth[v])
    {
        return u;
    }
    return v;
}
long long dis(int u, int v)
{
    return sum[u] + sum[v] - 2 * sum[LCA(u, v)];
}
void CenDFS(int u, int p)
{
    sz[u] = 1;
    for (auto l : Adj[u])
    {
        int v = l.first, w = l.second;
        if (visited[v] || v == p)
        {
            continue;
        }
        CenDFS(v, u);
        sz[u] += sz[v];
    }
}
int Find_Centroid(int u, int p, int x)
{
    for (auto l : Adj[u])
    {
        int v = l.first, w = l.second;
        if (visited[v] || v == p)
        {
            continue;
        }
        if (sz[v] > x/2)
        {
            return Find_Centroid(v, u, x);
        }
    }
    return u;
}
int BuildCentroid(int u)
{
    CenDFS(u, -1);
    int root = Find_Centroid(u, -1, sz[u]);
    visited[root] = true;
    //cerr << root << '\n';
    for (auto l : Adj[root])
    {
        int v = l.first, w = l.second;
        if (visited[v])
        {
            continue;
        }
        par[BuildCentroid(v)] = root;
    }
    return root;
}
void Init(int N, int A[], int B[], int D[])
{
    for (int i = 0; i < N - 1; ++ i)
    {
        Adj[A[i]].push_back({B[i], D[i]});
        Adj[B[i]].push_back({A[i], D[i]});
    }
    logg[0] = -1;
    DFS(0, -1);
    par[BuildCentroid(0)] = -1;
    for (int k = 1; k <= logg[timer]; ++ k)
    {
        for (int i = 1; i <= timer; ++ i)
        {
            int j = i + (1 << (k - 1));
            if (j > timer)
            {
                f[i][k] = f[i][k - 1];
            }
            else
            {
                int u = f[i][k - 1], v = f[j][k - 1];
                if (depth[u] < depth[v])
                {
                    f[i][k] = u;
                }
                else
                {
                    f[i][k] = v;
                }
            }
        }
    }
}
void update(int u, int t)
{
    for (int v = u; v != -1; v = par[v])
    {
        if (t)
        {
            dp[v] = min(dp[v], dis(u, v));
        }
        else
        {
            dp[v] = oo;
        }
    }
}
long long get(int u)
{
    long long ret = oo;
    for (int v = u; v != -1; v = par[v])
    {
        ret = min(ret, dp[v] + dis(u, v));
    }
    return ret;
}
long long Query(int S, int X[], int T, int Y[])
{
    long long res = oo;
    for (int i = 0; i < S; ++ i)
    {
        update(X[i], 1);
    }
    for (int i = 0; i < T; ++ i)
    {
        res = min(res, get(Y[i]));
    }
    for (int i = 0; i < S; ++ i)
    {
        update(X[i], 0);
    }
    return res;
}
/*void read()
{
    int A[] = {0, 1, 2, 2, 4, 1};
    int B[] = {1, 2, 3, 4, 5, 6};
    int D[] = {4, 4, 5, 6, 5, 3};
    Init(7, A, B, D);
    int X[] = {0, 1, 3};
    int Y[] = {4, 6};
    cout << Query(3, X, 2, Y);
}
void solve()
{
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}*/

Compilation message (stderr)

factories.cpp: In function 'void CenDFS(int, int)':
factories.cpp:59:26: warning: unused variable 'w' [-Wunused-variable]
   59 |         int v = l.first, w = l.second;
      |                          ^
factories.cpp: In function 'int Find_Centroid(int, int, int)':
factories.cpp:72:26: warning: unused variable 'w' [-Wunused-variable]
   72 |         int v = l.first, w = l.second;
      |                          ^
factories.cpp: In function 'int BuildCentroid(int)':
factories.cpp:92:26: warning: unused variable 'w' [-Wunused-variable]
   92 |         int v = l.first, w = l.second;
      |                          ^

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