oj.uz

Submission #993779

# Submission time Handle Problem Language Result Execution time Memory
993779 2024-06-06T12:09:34 Z gortomi Factories (JOI14_factories) C++17
100 / 100
 3405 ms 273720 KB 
#include <bits/stdc++.h>
#include "factories.h"

//#include "grader.cpp"
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
vector<vector<pii> > g;
vector<bool> vis;
vector<int> s;
vector<vector<ll> > d;
vector<vector<int> > pa;
vector<ll> mini;
void calc(int v, int p)
{
    s[v] = 1;
    for(auto [x, w] : g[v])
    {
        if(vis[x]) continue;
        if(x == p) continue;
        calc(x, v);
        s[v] += s[x];
    }
}
int findc(int v, int p, int bp)
{

    for(auto [x, w] : g[v])
    {
        if(x == p || vis[x]) continue;
        if(s[bp] / 2 < s[x]) return findc(x, v, bp);
    }
    return v;
}
void calc2(int v, int p, ll dep, int l, int bp)
{
    pa[v][l] = bp;
    d[v][l] = dep;
    for(auto [x, w] : g[v])
    {
        if(x == p || vis[x]) continue;
        calc2(x, v, dep + w, l, bp);
    }
}
void dec(int v, int l)
{

    calc(v, -1);
    int c = findc(v, -1, v);
    vis[c] = 1;
    calc2(c, -1, 0, l, c);

    for(auto [x, w] : g[c])
    {

        if(!vis[x]) dec(x, l + 1);

    }
}
ll Query(int t, int b[], int s, int a[])
{
    vector<int> ve;
    for(int i = 0; i < s; i++)
    {
        int x = a[i];
        for(int j = 0; j < 20; j++)
        {
            int v = pa[x][j];
            if(v != -1)
            {
                mini[v] = min(mini[v], d[x][j]);
                ve.push_back(v);
            }
        }
    }
    ll ans = 1e15;
    for(int i = 0; i < t; i++)
    {
        int x = b[i];
        ll act = 1e15;
        for(int j = 0; j < 20; j++)
        {
            int v = pa[x][j];
            if(v != -1)
            {
                act = min(act, mini[v] + d[x][j]);
            }
        }
        ans = min(act, ans);
    }
    for(auto x : ve) mini[x] = 1e15;
    return ans;
}
void Init(int n, int a[], int b[], int c[])
//int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    /*
    int n, q;
    cin >> n >> q;
    //*/
    g.resize(n);
    vis.resize(n);
    s.resize(n);
    d.resize(n, vector<ll>(20));
    pa.resize(n, vector<int>(20, -1));
    mini.resize(n, 1e15);
    for(int i = 0; i < n - 1; i++)
    {
        ll x = a[i], y = b[i], w = c[i];
        /*
        int x, y, w;
        cin >> x >> y >> w;
        //*/
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    dec(0, 0);
    /*
    while(q--)
    {
        int s, t;
        cin >> s >> t;
        int a[s], b[t];
        for(int i = 0; i < s; i++) cin >> a[i];
        for(int i = 0; i < t; i++) cin >> b[i];
        cout << Query(s, a, t, b) << "\n";
    }//*/
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1116 KB Output is correct
2 Correct 288 ms 20008 KB Output is correct
3 Correct 297 ms 20004 KB Output is correct
4 Correct 265 ms 20056 KB Output is correct
5 Correct 306 ms 20456 KB Output is correct
6 Correct 260 ms 19796 KB Output is correct
7 Correct 271 ms 19928 KB Output is correct
8 Correct 293 ms 20432 KB Output is correct
9 Correct 304 ms 20460 KB Output is correct
10 Correct 218 ms 19792 KB Output is correct
11 Correct 283 ms 19776 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 712 KB Output is correct
2 Correct 1814 ms 231776 KB Output is correct
3 Correct 2376 ms 234708 KB Output is correct
4 Correct 881 ms 229036 KB Output is correct
5 Correct 2965 ms 266200 KB Output is correct
6 Correct 2414 ms 236488 KB Output is correct
7 Correct 856 ms 65492 KB Output is correct
8 Correct 453 ms 65220 KB Output is correct
9 Correct 853 ms 70224 KB Output is correct
10 Correct 806 ms 66896 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1116 KB Output is correct
2 Correct 288 ms 20008 KB Output is correct
3 Correct 297 ms 20004 KB Output is correct
4 Correct 265 ms 20056 KB Output is correct
5 Correct 306 ms 20456 KB Output is correct
6 Correct 260 ms 19796 KB Output is correct
7 Correct 271 ms 19928 KB Output is correct
8 Correct 293 ms 20432 KB Output is correct
9 Correct 304 ms 20460 KB Output is correct
10 Correct 218 ms 19792 KB Output is correct
11 Correct 283 ms 19776 KB Output is correct
12 Correct 2 ms 712 KB Output is correct
13 Correct 1814 ms 231776 KB Output is correct
14 Correct 2376 ms 234708 KB Output is correct
15 Correct 881 ms 229036 KB Output is correct
16 Correct 2965 ms 266200 KB Output is correct
17 Correct 2414 ms 236488 KB Output is correct
18 Correct 856 ms 65492 KB Output is correct
19 Correct 453 ms 65220 KB Output is correct
20 Correct 853 ms 70224 KB Output is correct
21 Correct 806 ms 66896 KB Output is correct
22 Correct 2049 ms 242720 KB Output is correct
23 Correct 2148 ms 241512 KB Output is correct
24 Correct 2926 ms 249800 KB Output is correct
25 Correct 2949 ms 251888 KB Output is correct
26 Correct 2698 ms 243120 KB Output is correct
27 Correct 3405 ms 273720 KB Output is correct
28 Correct 1116 ms 240288 KB Output is correct
29 Correct 2797 ms 242940 KB Output is correct
30 Correct 2850 ms 242032 KB Output is correct
31 Correct 2788 ms 242824 KB Output is correct
32 Correct 932 ms 76360 KB Output is correct
33 Correct 421 ms 66752 KB Output is correct
34 Correct 525 ms 63060 KB Output is correct
35 Correct 522 ms 63036 KB Output is correct
36 Correct 754 ms 64068 KB Output is correct
37 Correct 707 ms 64016 KB Output is correct