oj.uz

Submission #284471

# Submission time Handle Problem Language Result Execution time Memory
284471 2020-08-27T13:01:15 Z HynDuf Factories (JOI14_factories) C++14
15 / 100
 8000 ms 113804 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define task "J"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 5e5 + 2;
vii g[N];
bool in[N];
int sz[N], dep[N], pa[N][19], par[N];
ll d[N], mnd[N];
void dfs(int u, int p)
{
    dep[u] = dep[p] + 1;
    pa[u][0] = p;
    rep(k, 1, 18) pa[u][k] = pa[pa[u][k - 1]][k - 1];
    for (ii v : g[u]) if (v.F != p)
    {
        d[v.F] = d[u] + v.S;
        dfs(v.F, u);
    }
}
int getsz(int u, int p)
{
    sz[u] = 1;
    for (ii v : g[u]) if (v.F != p && !in[v.F]) sz[u] += getsz(v.F, u);
    return sz[u];
}
int fcen(int u, int p, int nn)
{
    for (ii v : g[u]) if (v.F != p && !in[v.F] && sz[v.F] > nn / 2) return fcen(v.F, u, nn);
    return u;
}
int cd(int u)
{
    int nn = getsz(u, 0);
    u = fcen(u, 0, nn);
    in[u] = 1;
    for (ii v : g[u]) if (!in[v.F]) par[cd(v.F)] = u;
    return u;
}
int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    Rep(k, 18, 0) if (dep[pa[x][k]] >= dep[y]) x = pa[x][k];
    if (x == y) return x;
    Rep(k, 18, 0) if (pa[x][k] != pa[y][k]) x = pa[x][k], y = pa[y][k];
    return pa[x][0];
}
void Init(int n, int A[], int B[], int D[])
{
    rep(i, 0, n - 2) g[A[i] + 1].eb(B[i] + 1, D[i]), g[B[i] + 1].eb(A[i] + 1, D[i]);
    dfs(1, 0);
    cd(1);
    fill(mnd + 1, mnd + 1 + n, 1e18);
}
ll Query(int S, int X[], int T, int Y[])
{
    ll ans = 1e18;
    rep(i, 0, S - 1)
    {
        int u = X[i] + 1;
        while (u)
        {
            mnd[u] = min(mnd[u], d[X[i] + 1] + d[u] - 2 * d[lca(X[i] + 1, u)]);
            u = par[u];
        }
    }
    rep(i, 0, T - 1)
    {
        int u = Y[i] + 1;
        while (u)
        {
            ans = min(ans, d[Y[i] + 1] + d[u] - 2 * d[lca(Y[i] + 1, u)] + mnd[u]);
            u = par[u];
        }
    }
    rep(i, 0, S - 1)
    {
        int u = X[i] + 1;
        while (u)
        {
            mnd[u] = 1e18;
            u = par[u];
        }
    }
    return ans;
}
//int n, q, A[100], B[100], D[100], S, T, X[100], Y[100];
//int main()
//{
//#ifdef HynDuf
//    freopen(task".in", "r", stdin);
//    //freopen(task".out", "w", stdout);
//#else
//    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//#endif
//    cin >> n >> q;
//    rep(i, 0, n - 2) cin >> A[i] >> B[i] >> D[i];
//    Init(n, A, B, D);
//    while (q--)
//    {
//        cin >> S >> T;
//        rep(i, 0, S - 1) cin >> X[i];
//        rep(i, 0, T - 1) cin >> Y[i];
//        cout << Query(S, X, T, Y) << '\n';
//    }
//    return 0;
//}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12672 KB Output is correct
2 Correct 2025 ms 30328 KB Output is correct
3 Correct 3366 ms 30456 KB Output is correct
4 Correct 3331 ms 30456 KB Output is correct
5 Correct 3561 ms 30600 KB Output is correct
6 Correct 818 ms 30328 KB Output is correct
7 Correct 3250 ms 30712 KB Output is correct
8 Correct 3437 ms 30600 KB Output is correct
9 Correct 3588 ms 30712 KB Output is correct
10 Correct 766 ms 30456 KB Output is correct
11 Correct 3252 ms 30704 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 4603 ms 113804 KB Output is correct
3 Execution timed out 8010 ms 113108 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12672 KB Output is correct
2 Correct 2025 ms 30328 KB Output is correct
3 Correct 3366 ms 30456 KB Output is correct
4 Correct 3331 ms 30456 KB Output is correct
5 Correct 3561 ms 30600 KB Output is correct
6 Correct 818 ms 30328 KB Output is correct
7 Correct 3250 ms 30712 KB Output is correct
8 Correct 3437 ms 30600 KB Output is correct
9 Correct 3588 ms 30712 KB Output is correct
10 Correct 766 ms 30456 KB Output is correct
11 Correct 3252 ms 30704 KB Output is correct
12 Correct 14 ms 12288 KB Output is correct
13 Correct 4603 ms 113804 KB Output is correct
14 Execution timed out 8010 ms 113108 KB Time limit exceeded
15 Halted 0 ms 0 KB -