oj.uz

Submission #550551

# Submission time Handle Problem Language Result Execution time Memory
550551 2022-04-18T13:20:16 Z Tien_Noob Factories (JOI14_factories) C++17
100 / 100
 6023 ms 174792 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 13 ms 12628 KB Output is correct
2 Correct 346 ms 23704 KB Output is correct
3 Correct 426 ms 23828 KB Output is correct
4 Correct 432 ms 23856 KB Output is correct
5 Correct 491 ms 24040 KB Output is correct
6 Correct 222 ms 23792 KB Output is correct
7 Correct 396 ms 23852 KB Output is correct
8 Correct 420 ms 23756 KB Output is correct
9 Correct 475 ms 24140 KB Output is correct
10 Correct 223 ms 23736 KB Output is correct
11 Correct 394 ms 23792 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2090 ms 144092 KB Output is correct
3 Correct 2900 ms 144296 KB Output is correct
4 Correct 940 ms 145032 KB Output is correct
5 Correct 3875 ms 174792 KB Output is correct
6 Correct 2986 ms 153320 KB Output is correct
7 Correct 1370 ms 60320 KB Output is correct
8 Correct 486 ms 61196 KB Output is correct
9 Correct 1718 ms 64736 KB Output is correct
10 Correct 1471 ms 61916 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12628 KB Output is correct
2 Correct 346 ms 23704 KB Output is correct
3 Correct 426 ms 23828 KB Output is correct
4 Correct 432 ms 23856 KB Output is correct
5 Correct 491 ms 24040 KB Output is correct
6 Correct 222 ms 23792 KB Output is correct
7 Correct 396 ms 23852 KB Output is correct
8 Correct 420 ms 23756 KB Output is correct
9 Correct 475 ms 24140 KB Output is correct
10 Correct 223 ms 23736 KB Output is correct
11 Correct 394 ms 23792 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2090 ms 144092 KB Output is correct
14 Correct 2900 ms 144296 KB Output is correct
15 Correct 940 ms 145032 KB Output is correct
16 Correct 3875 ms 174792 KB Output is correct
17 Correct 2986 ms 153320 KB Output is correct
18 Correct 1370 ms 60320 KB Output is correct
19 Correct 486 ms 61196 KB Output is correct
20 Correct 1718 ms 64736 KB Output is correct
21 Correct 1471 ms 61916 KB Output is correct
22 Correct 2947 ms 145848 KB Output is correct
23 Correct 3033 ms 148216 KB Output is correct
24 Correct 4311 ms 149036 KB Output is correct
25 Correct 4388 ms 152192 KB Output is correct
26 Correct 4388 ms 149428 KB Output is correct
27 Correct 6023 ms 173440 KB Output is correct
28 Correct 1269 ms 149568 KB Output is correct
29 Correct 4822 ms 148996 KB Output is correct
30 Correct 4677 ms 148256 KB Output is correct
31 Correct 4759 ms 149488 KB Output is correct
32 Correct 2314 ms 65724 KB Output is correct
33 Correct 581 ms 61424 KB Output is correct
34 Correct 1228 ms 58172 KB Output is correct
35 Correct 1166 ms 58196 KB Output is correct
36 Correct 1531 ms 58860 KB Output is correct
37 Correct 1543 ms 58852 KB Output is correct