Submission #550549

#	Time	Username	Problem	Language	Result	Execution time	Memory
550549		Tien_Noob	Factories (JOI14_factories)	C++17	15 / 100	8028 ms	132420 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 = 18;
const long long oo = 1e18;
vector<pair<int, int> > Adj[N + 1];
long long dp[N + 1], sum[N + 1];
int f[N + 1][cbit + 1], par[N + 1], sz[N + 1], depth[N + 1];
bool visited[N + 1];
void DFS(int u, int p)
{
    dp[u] = oo;
    for (auto x : Adj[u])
    {
        int v = x.first, w = x.second;
        if (v == p)
        {
            continue;
        }
        depth[v] = depth[u] + 1;
        sum[v] = sum[u] + w;
        f[v][0] = u;
        for (int i = 1; i <= cbit; ++ i)
        {
            f[v][i] = f[f[v][i - 1]][i - 1];
        }
        DFS(v, u);
    }
}
int LCA(int u, int v)
{
    if (depth[u] > depth[v])
    {
        swap(u, v);
    }
    int k = depth[v] - depth[u];
    for (int i = cbit; i >= 0; -- i)
    {
        if ((k >> i) & 1)
        {
            v = f[v][i];
        }
    }
    if (u == v)
    {
        return u;
    }
    for (int i = cbit; i >= 0; -- i)
    {
        if (f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
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]});
    }
    DFS(0, -1);
    par[BuildCentroid(0)] = -1;
}
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:71:26: warning: unused variable 'w' [-Wunused-variable]
   71 |         int v = l.first, w = l.second;
      |                          ^
factories.cpp: In function 'int Find_Centroid(int, int, int)':
factories.cpp:84:26: warning: unused variable 'w' [-Wunused-variable]
   84 |         int v = l.first, w = l.second;
      |                          ^
factories.cpp: In function 'int BuildCentroid(int)':
factories.cpp:104:26: warning: unused variable 'w' [-Wunused-variable]
  104 |         int v = l.first, w = l.second;
      |                          ^

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