oj.uz

Submission #256867

# Submission time Handle Problem Language Result Execution time Memory
256867 2020-08-03T10:29:28 Z TeaTime Factories (JOI14_factories) C++17
0 / 100
 9 ms 1024 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 5e5 + 10, INF = 1e9;
ll sizes[SZ];
bool used[SZ];
vector<vector<pair<ll,  ll>>> vec;

vector<vector<pair<ll, ll>>> gr;
ll curC = 0;
vector<ll> bst;
set<ll> u;

ll sz(int v, int dist = 0, int par = -1) {
    ll s = 1;
    vec[v].push_back({curC, dist});

    for (auto to : gr[v]) {
        if (!used[to.first] && to.first != par) {
            s += sz(to.first, dist + to.second, v);
        }
    }

    sizes[v] = s;
    return s;
}

ll cntr(int v, int c) {
    for (auto to : gr[v]) {
        if (!used[to.first] && sizes[to.first] >= c / 2) {
            return cntr(to.first, c);
        }
    }

    return v;
}

void decomp(int v) {
    used[v] = 1;
    curC = v;
    sz(v);

    for (auto to : gr[v]) {
        if (!used[to.first]) {
            decomp(cntr(to.first, sizes[to.first]));
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    gr.resize(N);
    for (int i = 0; i < N - 1; i++) {
        gr[A[i]].push_back({B[i], D[i]});
        gr[B[i]].push_back({A[i], D[i]});
    }

    bst.resize(N);
    for (auto &c : bst) c = INF;
    decomp(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i =  0; i < S; i++) {
        ll ind = X[i];
        for (auto cur : vec[ind]) {
            u.insert(cur.first);
            bst[cur.first] = min(bst[cur.first], cur.second);
        }
    }

    ll ans = INF;
    for (int i =  0; i < T; i++) {
        ll ind = Y[i];
        for (auto cur : vec[ind]) {
           ans = min(ans, bst[cur.first] + cur.second);
        }
    }
    for (auto cur : u) bst[cur] = INF;
    u.clear();
    return ans;
}

/*int main()
{
    fastInp;

    ll n;
    cin >> n;

    for (int i = 0; i < n; i++) {

    }

    return 0;
}*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -