oj.uz

Submission #1111288

# Submission time Handle Problem Language Result Execution time Memory
1111288 2024-11-12T01:56:46 Z ljtunas Factories (JOI14_factories) C++17
33 / 100
 8000 ms 216008 KB 
// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v)    memset(h, v, sizeof h)
#define Forv(i, a)     for(auto& i : a)
#define For(i, a, b)   for(int i = a; i <= b; ++i)
#define Ford(i, a, b)  for(int i = a; i >= b; --i)
#define c_bit(i)     __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1LL)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
using namespace std;
namespace std {
    template <typename T, int D>
    struct _vector : public vector <_vector <T, D - 1>> {
        static_assert(D >= 1, "Dimension must be positive!");
        template <typename... Args>
        _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
    };
    template <typename T> struct _vector <T, 1> : public vector <T> {
        _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
    };
    template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
    template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 1e6 + 5;
const  ll  mod = 1e9 + 7;
const  ll   oo = 1e18;

//#define int long long

int sz[MAXN], p[MAXN]; bool del[MAXN];
vector<ii> g[MAXN];


int dep[MAXN], pre[MAXN][22]; ll d[MAXN];

void dfs(int u, int par) {
    pre[u][0] = par, sz[u] = 1;
    For(k, 1, 20) pre[u][k] = pre[pre[u][k - 1]][k - 1];
    for(auto [v, w] : g[u]) {
        if (v == par) continue;
        dep[v] = dep[u] + 1;
        d[v] = d[u] + w;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int getlca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int len = dep[u] - dep[v];
    For(k, 0, 20) if (Bit(len, k)) u = pre[u][k];
    if (u == v) return u;
    Ford(k, 20, 0) if (pre[u][k] != pre[v][k])
        u = pre[u][k], v = pre[v][k];
    return pre[u][0];
}

ll dist(int u, int v){
    return d[u] + d[v] - 2 * d[getlca(u, v)];
}

void dfsSize(int u, int par){
    sz[u] = 1;
    for(auto [v, w] : g[u]) if((v ^ par) && !del[v]){
        dfsSize(v, u);
        sz[u] += sz[v];
    }
}

int find(int u, int par, int n){
    for(auto [v, w] : g[u])if(v ^ par){
        if(sz[v] > n / 2 && !del[v]) return find(v, u, n);
    }
    return u;
}


void buildCentroid(int u, int par){
    dfsSize(u, par);
    int c = find(u, par, sz[u]);
    del[c] = true;
    p[c] = par;
    for(auto [v, _] : g[c]) if((v ^ par) && !del[v]) {
        buildCentroid(v, c);
    }
}

multiset<ll> res[MAXN]; bool op[MAXN];

void update(int u){
    int v = u;
    op[u] ^= 1;
    while(v){
        if(op[u]) res[v].insert({dist(u, v)});
        else res[v].erase({dist(u, v)});
        v = p[v];
    }
    if(op[u]) res[v].insert({dist(u, v)});
    else res[v].erase({dist(u, v)});
}

ll get(int u){
    int v = u;
    ll ans = oo;
    while(v){
        if(res[v].size()){
            auto it = res[v].begin();
            minimize(ans, *it + dist(u, v));
        }
        v = p[v];
    }
    if(res[v].size()) {
        auto it = res[v].begin();
        minimize(ans, *it + dist(u, v));
    }
    return ans;
}

long long Query(int S, int X[], int T, int Y[]){


//    cin >> S;
//    cin >> T;
//    For(i, 0, S - 1) cin >> X[i];
//    For(i, 0, T - 1) cin >> Y[i];
    For(i, 0, S - 1){
        int u = X[i] + 1;
        update(u);
    }
    ll ans = oo;
    For(i, 0, T - 1){
        minimize(ans, get(Y[i] + 1));
    }
     For(i, 0, S - 1){
        int u = X[i] + 1;
        update(u);
    }
    return ans;
}

int n, a[MAXN], b[MAXN], w[MAXN], S, T, x[MAXN], y[MAXN];

void Init(int n, int a[], int b[], int w[]){
//    cin >> n;
//    int q; cin >> q;
//    For(i, 0, n - 2) {
//        cin >> a[i] >> b[i] >> w[i];
//    }
    For(i, 0, n - 2){
        ++a[i], ++b[i];
        g[a[i]].push_back({b[i], w[i]});
        g[b[i]].push_back({a[i], w[i]});
    }
    dfs(1, 0);
    buildCentroid(1, 0);
//    while(q--){
//        cout << Query(S, x, T, y) << '\n';
//    }
}

//void Solve() {
////    int q; cin >> q;
//    Init(n, a, b, w);
//}
//
//int32_t main() {
//    cin.tie(0) -> sync_with_stdio(0);
//    if(fopen("JOI14_factories.inp", "r")) {
//        freopen("JOI14_factories.inp", "r", stdin);
//        freopen("JOI14_factories.out", "w", stdout);
//    }
//
//    int t = 1;
////    cin >> t;
//
//    for (int test = 1; test <= t; test++) {
//        Solve();
//    }
//    return 0;
//}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 71240 KB Output is correct
2 Correct 2095 ms 84276 KB Output is correct
3 Correct 2989 ms 88592 KB Output is correct
4 Correct 3680 ms 91228 KB Output is correct
5 Correct 4417 ms 90380 KB Output is correct
6 Correct 761 ms 87048 KB Output is correct
7 Correct 2846 ms 87624 KB Output is correct
8 Correct 3241 ms 87764 KB Output is correct
9 Correct 4240 ms 90228 KB Output is correct
10 Correct 758 ms 86732 KB Output is correct
11 Correct 3012 ms 89328 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 70984 KB Output is correct
2 Correct 2474 ms 180812 KB Output is correct
3 Correct 5242 ms 183984 KB Output is correct
4 Correct 855 ms 179100 KB Output is correct
5 Correct 7250 ms 216008 KB Output is correct
6 Correct 5965 ms 186776 KB Output is correct
7 Correct 5334 ms 112012 KB Output is correct
8 Correct 844 ms 111800 KB Output is correct
9 Correct 5674 ms 116752 KB Output is correct
10 Correct 5623 ms 113396 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 71240 KB Output is correct
2 Correct 2095 ms 84276 KB Output is correct
3 Correct 2989 ms 88592 KB Output is correct
4 Correct 3680 ms 91228 KB Output is correct
5 Correct 4417 ms 90380 KB Output is correct
6 Correct 761 ms 87048 KB Output is correct
7 Correct 2846 ms 87624 KB Output is correct
8 Correct 3241 ms 87764 KB Output is correct
9 Correct 4240 ms 90228 KB Output is correct
10 Correct 758 ms 86732 KB Output is correct
11 Correct 3012 ms 89328 KB Output is correct
12 Correct 54 ms 70984 KB Output is correct
13 Correct 2474 ms 180812 KB Output is correct
14 Correct 5242 ms 183984 KB Output is correct
15 Correct 855 ms 179100 KB Output is correct
16 Correct 7250 ms 216008 KB Output is correct
17 Correct 5965 ms 186776 KB Output is correct
18 Correct 5334 ms 112012 KB Output is correct
19 Correct 844 ms 111800 KB Output is correct
20 Correct 5674 ms 116752 KB Output is correct
21 Correct 5623 ms 113396 KB Output is correct
22 Execution timed out 8052 ms 213576 KB Time limit exceeded
23 Halted 0 ms 0 KB -