oj.uz

Submission #897827

# Submission time Handle Problem Language Result Execution time Memory
897827 2024-01-03T18:16:24 Z ShaShi Factories (JOI14_factories) C++17
100 / 100
 3684 ms 404580 KB 
#include "factories.h"
#include <bits/stdc++.h>
// #define int long long 
#define F first
#define S second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pb push_back


using namespace std;
typedef long long ll;

const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e18 + 7;


int n, m, t, k, q, u, v, w, tmp, tmp2, tmp3, tmp4, tmp5, ans2, flag;
ll ans;
int arr[MAXN], sz[MAXN];
bool hate[MAXN];
pair<pair<ll, int>, pair<ll, int> > love[MAXN];
vector<pii> adj[MAXN];
vector<pair<int, ll> > vec[MAXN];



void DFSsz(int v, int p=-1) {
    sz[v] = 1;

    for (auto cur:adj[v]) {
        int u = cur.F;
        if (!hate[u] && u != p) {
            DFSsz(u, v);
            sz[v] += sz[u];
        }
    }
}


int centroid(int tot, int v, int p=-1) {
    for (auto cur:adj[v]) {
        int u = cur.F;
        if (!hate[u] && u != p && 2*sz[u] > tot) return centroid(tot, u, v);
    }

    return v;
}


void all_i_want(int cent, int v, int p, ll dis) {
    for (auto cur:adj[v]) {
        ll u = cur.F, w = cur.S;
        if (!hate[u] && u != p) all_i_want(cent, u, v, dis+w);
    }

    vec[v].pb(mp(cent, dis));
}



void solve(int v) {
    DFSsz(v);
    int cent = centroid(sz[v], v);

    hate[cent] = 1;
    for (auto cur:adj[cent]) {
        int u = cur.F, w = cur.S;

        if (!hate[u]) all_i_want(cent, u, cent, w);
    }

    vec[cent].pb(mp(cent, 0));

    for (auto cur:adj[cent]) {
        int u = cur.F;
        if (!hate[u]) solve(u);
    }
}


void add(int v, bool x=0) {
    for (auto cur:vec[v]) {
        ll u = cur.F, w = cur.S;

        if (x) {
            if (love[u].F.S != flag) {
                love[u].F.S = flag;
                love[u].F.F = w;
            } else {
                love[u].F.F = min(love[u].F.F, w);
            }
        } else {
            if (love[u].S.S != flag) {
                love[u].S.S = flag;
                love[u].S.F = w;
            } else {
                love[u].S.F = min(love[u].S.F, w);
            }
        }

        if (love[u].F.S == love[u].S.S && love[u].S.S == flag) ans = min(ans, love[u].F.F+love[u].S.F);
    }
}



void Init(int N, int A[], int B[], int D[]) {
    // cin >> n >> q;
    n = N;

    for (int i=1; i<n; i++) {
        // cin >> u >> v >> w;
        u = A[i-1]; v = B[i-1]; w = D[i-1];
        u++; v++;

        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }

    solve(1);
}

long long Query(int SS, int X[], int T, int Y[]) {
    flag++;
    ans = INF;
    
    for (int i=0; i<SS; i++) {
        u = X[i]; u++;
        add(u, 0);
    }

    for (int i=0; i<T; i++) {
        v = Y[i]; v++;
        add(v, 1);
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 68444 KB Output is correct
2 Correct 243 ms 82884 KB Output is correct
3 Correct 268 ms 83320 KB Output is correct
4 Correct 262 ms 83128 KB Output is correct
5 Correct 274 ms 83536 KB Output is correct
6 Correct 163 ms 82368 KB Output is correct
7 Correct 262 ms 83280 KB Output is correct
8 Correct 267 ms 83288 KB Output is correct
9 Correct 276 ms 83908 KB Output is correct
10 Correct 165 ms 82348 KB Output is correct
11 Correct 262 ms 83284 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 68444 KB Output is correct
2 Correct 1655 ms 255764 KB Output is correct
3 Correct 2538 ms 326560 KB Output is correct
4 Correct 597 ms 152600 KB Output is correct
5 Correct 3270 ms 404580 KB Output is correct
6 Correct 2731 ms 326312 KB Output is correct
7 Correct 784 ms 121440 KB Output is correct
8 Correct 272 ms 98752 KB Output is correct
9 Correct 875 ms 135220 KB Output is correct
10 Correct 799 ms 122096 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 68444 KB Output is correct
2 Correct 243 ms 82884 KB Output is correct
3 Correct 268 ms 83320 KB Output is correct
4 Correct 262 ms 83128 KB Output is correct
5 Correct 274 ms 83536 KB Output is correct
6 Correct 163 ms 82368 KB Output is correct
7 Correct 262 ms 83280 KB Output is correct
8 Correct 267 ms 83288 KB Output is correct
9 Correct 276 ms 83908 KB Output is correct
10 Correct 165 ms 82348 KB Output is correct
11 Correct 262 ms 83284 KB Output is correct
12 Correct 13 ms 68444 KB Output is correct
13 Correct 1655 ms 255764 KB Output is correct
14 Correct 2538 ms 326560 KB Output is correct
15 Correct 597 ms 152600 KB Output is correct
16 Correct 3270 ms 404580 KB Output is correct
17 Correct 2731 ms 326312 KB Output is correct
18 Correct 784 ms 121440 KB Output is correct
19 Correct 272 ms 98752 KB Output is correct
20 Correct 875 ms 135220 KB Output is correct
21 Correct 799 ms 122096 KB Output is correct
22 Correct 2004 ms 258568 KB Output is correct
23 Correct 2057 ms 262200 KB Output is correct
24 Correct 2967 ms 330040 KB Output is correct
25 Correct 2806 ms 332820 KB Output is correct
26 Correct 2840 ms 331696 KB Output is correct
27 Correct 3684 ms 404236 KB Output is correct
28 Correct 789 ms 158972 KB Output is correct
29 Correct 2965 ms 330808 KB Output is correct
30 Correct 3052 ms 330764 KB Output is correct
31 Correct 2927 ms 331184 KB Output is correct
32 Correct 965 ms 135268 KB Output is correct
33 Correct 257 ms 98500 KB Output is correct
34 Correct 636 ms 114872 KB Output is correct
35 Correct 699 ms 115796 KB Output is correct
36 Correct 762 ms 120656 KB Output is correct
37 Correct 759 ms 120612 KB Output is correct