oj.uz

답안 #821812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821812 2023-08-11T17:42:23 Z PanosPask 공장들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -