oj.uz

Submission #570726

# Submission time Handle Problem Language Result Execution time Memory
570726 2022-05-31T07:32:34 Z YouAreMyGalaxy Factories (JOI14_factories) C++17
100 / 100
 5920 ms 194196 KB 
//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

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12628 KB Output is correct
2 Correct 381 ms 30856 KB Output is correct
3 Correct 472 ms 30760 KB Output is correct
4 Correct 505 ms 30896 KB Output is correct
5 Correct 502 ms 31032 KB Output is correct
6 Correct 241 ms 30836 KB Output is correct
7 Correct 442 ms 30800 KB Output is correct
8 Correct 446 ms 30856 KB Output is correct
9 Correct 545 ms 31152 KB Output is correct
10 Correct 227 ms 30876 KB Output is correct
11 Correct 456 ms 30888 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12356 KB Output is correct
2 Correct 2513 ms 160496 KB Output is correct
3 Correct 3290 ms 162132 KB Output is correct
4 Correct 1061 ms 160856 KB Output is correct
5 Correct 4384 ms 191424 KB Output is correct
6 Correct 3211 ms 164184 KB Output is correct
7 Correct 1686 ms 60420 KB Output is correct
8 Correct 525 ms 61140 KB Output is correct
9 Correct 1747 ms 64872 KB Output is correct
10 Correct 1547 ms 61776 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12628 KB Output is correct
2 Correct 381 ms 30856 KB Output is correct
3 Correct 472 ms 30760 KB Output is correct
4 Correct 505 ms 30896 KB Output is correct
5 Correct 502 ms 31032 KB Output is correct
6 Correct 241 ms 30836 KB Output is correct
7 Correct 442 ms 30800 KB Output is correct
8 Correct 446 ms 30856 KB Output is correct
9 Correct 545 ms 31152 KB Output is correct
10 Correct 227 ms 30876 KB Output is correct
11 Correct 456 ms 30888 KB Output is correct
12 Correct 8 ms 12356 KB Output is correct
13 Correct 2513 ms 160496 KB Output is correct
14 Correct 3290 ms 162132 KB Output is correct
15 Correct 1061 ms 160856 KB Output is correct
16 Correct 4384 ms 191424 KB Output is correct
17 Correct 3211 ms 164184 KB Output is correct
18 Correct 1686 ms 60420 KB Output is correct
19 Correct 525 ms 61140 KB Output is correct
20 Correct 1747 ms 64872 KB Output is correct
21 Correct 1547 ms 61776 KB Output is correct
22 Correct 3055 ms 167624 KB Output is correct
23 Correct 3080 ms 170348 KB Output is correct
24 Correct 4830 ms 170312 KB Output is correct
25 Correct 4689 ms 174184 KB Output is correct
26 Correct 4518 ms 170472 KB Output is correct
27 Correct 5920 ms 194196 KB Output is correct
28 Correct 1256 ms 171332 KB Output is correct
29 Correct 4901 ms 170324 KB Output is correct
30 Correct 4550 ms 169536 KB Output is correct
31 Correct 4560 ms 170124 KB Output is correct
32 Correct 2323 ms 65728 KB Output is correct
33 Correct 544 ms 61600 KB Output is correct
34 Correct 1179 ms 58188 KB Output is correct
35 Correct 1219 ms 58152 KB Output is correct
36 Correct 1517 ms 58964 KB Output is correct
37 Correct 1458 ms 58796 KB Output is correct