oj.uz

Submission #821812

# Submission time Handle Problem Language Result Execution time Memory
821812 2023-08-11T17:42:23 Z PanosPask Factories (JOI14_factories) C++14
15 / 100
 8000 ms 44276 KB 
#include "factories.h"
#include "vector"
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;

const ll INF = 1e18;

typedef pair<int, int> pi;

int N;
vector<int> subtree_size;
vector<vector<pi>> adj_list;
vector<bool> removed;

// Query dependent variables
// Minimum distance to a destination/source node
ll lc_min_dest, lc_min_source;
ll min_dest, min_source;
vector<bool> destination;
vector<bool> source;
ll ans;

int calc_sb_size(int node, int par, ll d)
{
    subtree_size[node] = 1;

    for (auto [neigh, w] : adj_list[node]) {
        if (neigh != par && !removed[neigh]) {
            subtree_size[node] += calc_sb_size(neigh, node, d + w);
        }
    }

    if (destination[node]) {
        ans = min(ans, d + min_source);
        lc_min_dest = min(lc_min_dest, d);
    }
    if (source[node]) {
        ans = min(ans, d + min_dest);
        lc_min_source = min(lc_min_source, d);
    }

    return subtree_size[node];
}

int find_centroid(int node, int par, int sz)
{
    for (auto [neigh, w] : adj_list[node]) {
        if (!removed[neigh] && neigh != par && subtree_size[neigh] > sz / 2)
            return find_centroid(neigh, node, sz);
    }

    return node;
}

void centroid_decompose(int node)
{
    int c = find_centroid(node, -1, subtree_size[node]);

    min_dest = min_source = INF;

    removed[c] = true;
    if (destination[c])
        min_dest = 0;
    if (source[c])
        min_source = 0;

    for (auto [neigh, w] : adj_list[c]) {
        if (removed[neigh])
            continue;

        lc_min_dest = lc_min_source = INF;
        calc_sb_size(neigh, -1, w);

        min_dest = min(min_dest, lc_min_dest);
        min_source = min(min_source, lc_min_source);
    }

    for (auto [neigh, w] : adj_list[c]) {
        if (removed[neigh])
            continue;

        centroid_decompose(neigh);
    }

    return;
}

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

    adj_list.resize(N);
    subtree_size.resize(N);
    removed.resize(N);

    for (int i = 0; i < N - 1; i++) {
        adj_list[A[i]].pb(mp(B[i], D[i]));
        adj_list[B[i]].pb(mp(A[i], D[i]));
    }
}

long long Query(int S, int X[], int T, int Y[])
{
    source.assign(N, false);
    destination.assign(N, false);
    removed.assign(N, false);

    for (int i = 0; i < S; i++)
        source[X[i]] = true;
    for (int i = 0; i < T; i++)
        destination[Y[i]] = true;

    ans = INF;
    min_dest = min_source = INF;
    calc_sb_size(0, -1, 0);
    centroid_decompose(0);

    return ans;
}

Compilation message

factories.cpp: In function 'int calc_sb_size(int, int, ll)':
factories.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'void centroid_decompose(int)':
factories.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^
factories.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 724 KB Output is correct
2 Correct 3868 ms 13532 KB Output is correct
3 Correct 6302 ms 13476 KB Output is correct
4 Correct 5993 ms 13500 KB Output is correct
5 Correct 7415 ms 13812 KB Output is correct
6 Correct 788 ms 13524 KB Output is correct
7 Correct 5825 ms 13532 KB Output is correct
8 Correct 6159 ms 13660 KB Output is correct
9 Correct 7214 ms 13816 KB Output is correct
10 Correct 809 ms 13672 KB Output is correct
11 Correct 5987 ms 13516 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 456 KB Output is correct
2 Execution timed out 8012 ms 44276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 724 KB Output is correct
2 Correct 3868 ms 13532 KB Output is correct
3 Correct 6302 ms 13476 KB Output is correct
4 Correct 5993 ms 13500 KB Output is correct
5 Correct 7415 ms 13812 KB Output is correct
6 Correct 788 ms 13524 KB Output is correct
7 Correct 5825 ms 13532 KB Output is correct
8 Correct 6159 ms 13660 KB Output is correct
9 Correct 7214 ms 13816 KB Output is correct
10 Correct 809 ms 13672 KB Output is correct
11 Correct 5987 ms 13516 KB Output is correct
12 Correct 17 ms 456 KB Output is correct
13 Execution timed out 8012 ms 44276 KB Time limit exceeded
14 Halted 0 ms 0 KB -