oj.uz

Submission #482899

# Submission time Handle Problem Language Result Execution time Memory
482899 2021-10-26T17:02:54 Z Karliver Factories (JOI14_factories) C++17
100 / 100
 4723 ms 365052 KB 
#include "factories.h"    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int MX = 5e5 + 100;
const ll inf = (ll)1e18;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}

bool R[MX];

int S[MX], N;

struct info {
    int v;
    ll d;
};
V<info> nd[MX];
V<PR<int>> cd(MX);
V<PR<int>> g[MX];
V<ll> mi(MX);

int dfs_sz(int v, int p = -1) {
    S[v] = 1;
    for(auto [c, w] : g[v]) {
        if(c == p || R[c])continue;
        S[v] += dfs_sz(c, v);
    }
    return S[v];
}

int get_cen(int v, int ms, int p = -1) {
    for(auto [c, w] : g[v])
        if(c != p && !R[c] && S[c] * 2 > ms)
            return get_cen(c, ms, v);
    
    return v;
}

void dfs1(int v, int p, int tp, ll d = 0) {
    nd[v].push_back({tp, d});
    for(auto [c, w] : g[v]) {
        if(c != p && !R[c]) {
            
            dfs1(c, v, tp, d + w);

        }
    }
    
}

void cen(int v = 1) {
    v = get_cen(v, dfs_sz(v));

    R[v] = 1;
    
    dfs1(v, v, v);

    for(auto [c, w] : g[v]) {
        if(!R[c])
            cen(c);
    }

}

void Init(int N, int *a, int *b, int *c) {
    
    forn(i, N - 1) {
        ++a[i], ++b[i];
        g[a[i]].push_back({b[i], c[i]});
        g[b[i]].push_back({a[i], c[i]});
    }
    for(int i = 1;i <= N;++i) mi[i] = inf;
    cen();
}

long long Query(int S, int *a, int T, int *b) {
    forn(i, S) a[i]++;
    forn(i, T) b[i]++;

    V<int> del;
    forn(i, S) {
        int x = a[i];
        for(auto p : nd[x]) {
            ckmi(mi[p.v], p.d);
            del.push_back(p.v);
        }
    }
    ll ret = inf;
    forn(i, T) {
        int x = b[i];
        for(auto p : nd[x]) {
            ckmi(ret, mi[p.v] + p.d);    
        }
    }
    for(auto c : del) mi[c] = inf;
    assert(ret != inf);
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32040 KB Output is correct
2 Correct 303 ms 50180 KB Output is correct
3 Correct 326 ms 46800 KB Output is correct
4 Correct 324 ms 47404 KB Output is correct
5 Correct 343 ms 47356 KB Output is correct
6 Correct 244 ms 45892 KB Output is correct
7 Correct 345 ms 46756 KB Output is correct
8 Correct 327 ms 46964 KB Output is correct
9 Correct 345 ms 47356 KB Output is correct
10 Correct 243 ms 45980 KB Output is correct
11 Correct 364 ms 46812 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31820 KB Output is correct
2 Correct 2436 ms 192660 KB Output is correct
3 Correct 3556 ms 279760 KB Output is correct
4 Correct 880 ms 106172 KB Output is correct
5 Correct 4669 ms 342904 KB Output is correct
6 Correct 3562 ms 271012 KB Output is correct
7 Correct 1062 ms 88144 KB Output is correct
8 Correct 461 ms 66152 KB Output is correct
9 Correct 1235 ms 101992 KB Output is correct
10 Correct 1096 ms 89576 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32040 KB Output is correct
2 Correct 303 ms 50180 KB Output is correct
3 Correct 326 ms 46800 KB Output is correct
4 Correct 324 ms 47404 KB Output is correct
5 Correct 343 ms 47356 KB Output is correct
6 Correct 244 ms 45892 KB Output is correct
7 Correct 345 ms 46756 KB Output is correct
8 Correct 327 ms 46964 KB Output is correct
9 Correct 345 ms 47356 KB Output is correct
10 Correct 243 ms 45980 KB Output is correct
11 Correct 364 ms 46812 KB Output is correct
12 Correct 18 ms 31820 KB Output is correct
13 Correct 2436 ms 192660 KB Output is correct
14 Correct 3556 ms 279760 KB Output is correct
15 Correct 880 ms 106172 KB Output is correct
16 Correct 4669 ms 342904 KB Output is correct
17 Correct 3562 ms 271012 KB Output is correct
18 Correct 1062 ms 88144 KB Output is correct
19 Correct 461 ms 66152 KB Output is correct
20 Correct 1235 ms 101992 KB Output is correct
21 Correct 1096 ms 89576 KB Output is correct
22 Correct 2486 ms 220136 KB Output is correct
23 Correct 2693 ms 227444 KB Output is correct
24 Correct 3966 ms 294536 KB Output is correct
25 Correct 4272 ms 296604 KB Output is correct
26 Correct 4000 ms 288456 KB Output is correct
27 Correct 4723 ms 365052 KB Output is correct
28 Correct 1082 ms 119364 KB Output is correct
29 Correct 3704 ms 287812 KB Output is correct
30 Correct 3749 ms 288004 KB Output is correct
31 Correct 3736 ms 287860 KB Output is correct
32 Correct 1137 ms 107144 KB Output is correct
33 Correct 414 ms 66928 KB Output is correct
34 Correct 754 ms 81004 KB Output is correct
35 Correct 770 ms 81708 KB Output is correct
36 Correct 952 ms 86620 KB Output is correct
37 Correct 941 ms 86496 KB Output is correct