oj.uz

Submission #993770

# Submission time Handle Problem Language Result Execution time Memory
993770 2024-06-06T12:04:34 Z gortomi Factories (JOI14_factories) C++17
0 / 100
 2706 ms 264464 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, 0);
    int c = findc(v, 0, v);
    vis[c] = 1;
    calc2(c, 0, 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(1, 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 244 ms 19284 KB Output is correct
3 Incorrect 248 ms 19072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 1570 ms 229772 KB Output is correct
3 Correct 2226 ms 232308 KB Output is correct
4 Correct 800 ms 227244 KB Output is correct
5 Correct 2706 ms 264464 KB Output is correct
6 Correct 2257 ms 234508 KB Output is correct
7 Correct 641 ms 64232 KB Output is correct
8 Incorrect 397 ms 63944 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 244 ms 19284 KB Output is correct
3 Incorrect 248 ms 19072 KB Output isn't correct
4 Halted 0 ms 0 KB -