oj.uz

Submission #993724

# Submission time Handle Problem Language Result Execution time Memory
993724 2024-06-06T10:38:13 Z gortomi Factories (JOI14_factories) C++17
0 / 100
 2384 ms 299284 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<long long> s;
vector<vector<ll> > d;
vector<vector<long long> > pa;
vector<ll> mini;
void calc(long long v, long long 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];
    }
}
long long findc(long long v, long long p, long long 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(long long v, long long p, ll dep, long long l, long long 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(long long v, long long l)
{

    calc(v, 0);
    long long 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<long long> ve;
    for(long long i = 0; i < s; i++)
    {
        long long x = a[i];
        for(long long j = 0; j < 20; j++)
        {
            long long v = pa[x][j];
            if(v != 0)
            {
                mini[v] = min(mini[v], d[x][j]);
                ve.push_back(v);
            }
        }
    }
    ll ans = 1e15;
    for(long long i = 0; i < t; i++)
    {
        long long x = b[i];
        ll act = 1e15;
        for(long long j = 0; j < 20; j++)
        {
            long long v = pa[x][j];
            if(v != 0)
            {
                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[])
{
    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<long long>(20));
    mini.resize(n, 1e15);
    for(long long 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 7 ms 16984 KB Output is correct
2 Correct 273 ms 23584 KB Output is correct
3 Incorrect 312 ms 23380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 1506 ms 264596 KB Output is correct
3 Correct 1916 ms 268880 KB Output is correct
4 Correct 776 ms 262384 KB Output is correct
5 Correct 2384 ms 299284 KB Output is correct
6 Correct 2105 ms 269516 KB Output is correct
7 Correct 742 ms 70664 KB Output is correct
8 Incorrect 553 ms 69736 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16984 KB Output is correct
2 Correct 273 ms 23584 KB Output is correct
3 Incorrect 312 ms 23380 KB Output isn't correct
4 Halted 0 ms 0 KB -