oj.uz

Submission #373145

# Submission time Handle Problem Language Result Execution time Memory
373145 2021-03-03T14:13:50 Z BartolM Factories (JOI14_factories) C++17
33 / 100
 8000 ms 148712 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int MAXN=5e5+5;
const int LOG=20;
const int OFF=(1<<19);

struct Tournament{
    ll tour[2*OFF];
    Tournament() {
        fill(tour, tour+2*OFF, MAX);
    }
    ll query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
        if (lo>=a && hi<=b) return tour[pos];
        if (lo>=b || hi<=a) return MAX;
        int mid=(lo+hi)/2;
        return min(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
    }
    void update(int pos, ll val) {
        pos+=OFF; tour[pos]=val;
        pos/=2;
        while (pos) {
            tour[pos]=min(tour[pos*2], tour[pos*2+1]);
            pos/=2;
        }
    }
};

int n, dtime=0;
ll dist[MAXN];
int par[LOG][MAXN], dep[MAXN], L[MAXN], R[MAXN];
vector <pii> ls[MAXN];
ll da[MAXN], db[MAXN];
vector <int> v;

int cmp(int a, int b) {
    return L[a]<L[b];
}

void dfs(int node, int rod, ll d) {
    par[0][node]=rod;
    dist[node]=d;
    dep[node]=dep[rod]+1;
    L[node]=dtime++;
//    printf("node: %d, dist: %lld, dep: %d, par: %d\n", node, dist[node], dep[node], rod);
    for (pii sus:ls[node]) if (sus.X!=rod) dfs(sus.X, node, d+sus.Y);
    R[node]=dtime;
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=0; j<n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void rek(int node) {
    for (pii sus:ls[node]) {
        if (sus.X!=par[0][node]) {
            rek(sus.X);
            da[node]=min(da[node], da[sus.X]+sus.Y);
            db[node]=min(db[node], db[sus.X]+sus.Y);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        ls[A[i]].pb(mp(B[i], D[i]));
        ls[B[i]].pb(mp(A[i], D[i]));
    }
    dfs(0, 0, 0);
    build();
}

Tournament TA, TB;

long long Query(int S, int x[], int T, int y[]) {
    v.clear();
    for (int i=0; i<S; ++i) {
        v.pb(x[i]);
        TA.update(L[x[i]], dist[x[i]]);
    }
    for (int i=0; i<T; ++i) {
        v.pb(y[i]);
        TB.update(L[y[i]], dist[y[i]]);
    }

    sort(v.begin(), v.end(), cmp);
    ll sol=MAX;
    for (int i=1; i<(int)v.size(); ++i) {
        int lc=lca(v[i-1], v[i]);
        ll curr=TA.query(L[lc], R[lc])+TB.query(L[lc], R[lc])-dist[lc]*2;
        sol=min(sol, curr);
    }
    for (int i=0; i<S; ++i) TA.update(L[x[i]], MAX);
    for (int i=0; i<T; ++i) TB.update(L[y[i]], MAX);
    return sol;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 29292 KB Output is correct
2 Correct 1938 ms 47172 KB Output is correct
3 Correct 2137 ms 46956 KB Output is correct
4 Correct 2005 ms 47032 KB Output is correct
5 Correct 1965 ms 47212 KB Output is correct
6 Correct 2021 ms 47012 KB Output is correct
7 Correct 2138 ms 47092 KB Output is correct
8 Correct 2004 ms 47084 KB Output is correct
9 Correct 1976 ms 47228 KB Output is correct
10 Correct 2013 ms 46960 KB Output is correct
11 Correct 2144 ms 47348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28908 KB Output is correct
2 Correct 3387 ms 124516 KB Output is correct
3 Correct 5014 ms 128596 KB Output is correct
4 Correct 2444 ms 127060 KB Output is correct
5 Correct 4177 ms 148712 KB Output is correct
6 Correct 5405 ms 127496 KB Output is correct
7 Correct 6453 ms 62528 KB Output is correct
8 Correct 3570 ms 67804 KB Output is correct
9 Correct 4847 ms 70688 KB Output is correct
10 Correct 6267 ms 68412 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 29292 KB Output is correct
2 Correct 1938 ms 47172 KB Output is correct
3 Correct 2137 ms 46956 KB Output is correct
4 Correct 2005 ms 47032 KB Output is correct
5 Correct 1965 ms 47212 KB Output is correct
6 Correct 2021 ms 47012 KB Output is correct
7 Correct 2138 ms 47092 KB Output is correct
8 Correct 2004 ms 47084 KB Output is correct
9 Correct 1976 ms 47228 KB Output is correct
10 Correct 2013 ms 46960 KB Output is correct
11 Correct 2144 ms 47348 KB Output is correct
12 Correct 23 ms 28908 KB Output is correct
13 Correct 3387 ms 124516 KB Output is correct
14 Correct 5014 ms 128596 KB Output is correct
15 Correct 2444 ms 127060 KB Output is correct
16 Correct 4177 ms 148712 KB Output is correct
17 Correct 5405 ms 127496 KB Output is correct
18 Correct 6453 ms 62528 KB Output is correct
19 Correct 3570 ms 67804 KB Output is correct
20 Correct 4847 ms 70688 KB Output is correct
21 Correct 6267 ms 68412 KB Output is correct
22 Correct 5600 ms 118804 KB Output is correct
23 Correct 6191 ms 121228 KB Output is correct
24 Correct 6093 ms 121068 KB Output is correct
25 Correct 6414 ms 124236 KB Output is correct
26 Execution timed out 8074 ms 120524 KB Time limit exceeded
27 Halted 0 ms 0 KB -