oj.uz

Submission #993813

# Submission time Handle Problem Language Result Execution time Memory
993813 2024-06-06T12:51:48 Z Peti Factories (JOI14_factories) C++14
100 / 100
 3392 ms 374168 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

int n;
const long long INF = 1e18;

vector<vector<pair<int, long long>>> g, cp;
vector<bool> vis;
vector<int> g_sz;

vector<long long> min_dist;

int dfs_sz(int x, int p = -1){
    g_sz[x] = 1;
    for(auto [y, _] : g[x]){
        if(y != p && !vis[y]){
            g_sz[x] += dfs_sz(y, x);
        }
    }
    return g_sz[x];
}

int dfs_c(int x, int sz, int p = -1){
    for(auto [y, _] : g[x]){
        if(y != p && !vis[y] && g_sz[y]*2 > sz){
            return dfs_c(y, sz, x);
        }
    }
    return x;
}

void dfs(int x, long long d, int c, int p = -1){
    cp[x].emplace_back(c, d);
    for(auto [y, w] : g[x]){
        if(y != p && !vis[y]){
            dfs(y, d + w, c, x);
        }
    }
}

void centroid_decomp(int x){
    int c = dfs_c(x, dfs_sz(x));
    dfs(c, 0, c);
    vis[c] = true;

    for(auto [y, _] : g[c]){
        if(!vis[y]){
            centroid_decomp(y);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
    g.assign(n, vector<pair<int, long long>>());
    cp.assign(n, vector<pair<int, long long>>());
    vis.assign(n, false);
    min_dist.assign(n, INF);
    g_sz.assign(n, 0);

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

    centroid_decomp(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> q;
    for(int i = 0; i < T; i++){
        int x = Y[i];
        for(auto [y, d] : cp[x]){
            min_dist[y] = min(min_dist[y], d);
            q.push_back(y);
        }
    }

    long long ans = INF;
    for(int i = 0; i < S; i++){
        int x = X[i];
        for(auto [y, d] : cp[x]){
            ans = min(ans, min_dist[y] + d);
        }
    }
    
    for(int x : q) min_dist[x] = INF;

	return ans;
}

Compilation message

factories.cpp: In function 'int dfs_sz(int, int)':
factories.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [y, _] : g[x]){
      |              ^
factories.cpp: In function 'int dfs_c(int, int, int)':
factories.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [y, _] : g[x]){
      |              ^
factories.cpp: In function 'void dfs(int, long long int, int, int)':
factories.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for(auto [y, w] : g[x]){
      |              ^
factories.cpp: In function 'void centroid_decomp(int)':
factories.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [y, _] : g[c]){
      |              ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         for(auto [y, d] : cp[x]){
      |                  ^
factories.cpp:84:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |         for(auto [y, d] : cp[x]){
      |                  ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 191 ms 27200 KB Output is correct
3 Correct 192 ms 22712 KB Output is correct
4 Correct 204 ms 22868 KB Output is correct
5 Correct 230 ms 23396 KB Output is correct
6 Correct 139 ms 21592 KB Output is correct
7 Correct 200 ms 22868 KB Output is correct
8 Correct 227 ms 23220 KB Output is correct
9 Correct 229 ms 23380 KB Output is correct
10 Correct 136 ms 21688 KB Output is correct
11 Correct 194 ms 22724 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 1512 ms 204504 KB Output is correct
3 Correct 2126 ms 287720 KB Output is correct
4 Correct 482 ms 105988 KB Output is correct
5 Correct 2673 ms 365996 KB Output is correct
6 Correct 2208 ms 285928 KB Output is correct
7 Correct 578 ms 68432 KB Output is correct
8 Correct 237 ms 44480 KB Output is correct
9 Correct 670 ms 81492 KB Output is correct
10 Correct 567 ms 68692 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 191 ms 27200 KB Output is correct
3 Correct 192 ms 22712 KB Output is correct
4 Correct 204 ms 22868 KB Output is correct
5 Correct 230 ms 23396 KB Output is correct
6 Correct 139 ms 21592 KB Output is correct
7 Correct 200 ms 22868 KB Output is correct
8 Correct 227 ms 23220 KB Output is correct
9 Correct 229 ms 23380 KB Output is correct
10 Correct 136 ms 21688 KB Output is correct
11 Correct 194 ms 22724 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 1512 ms 204504 KB Output is correct
14 Correct 2126 ms 287720 KB Output is correct
15 Correct 482 ms 105988 KB Output is correct
16 Correct 2673 ms 365996 KB Output is correct
17 Correct 2208 ms 285928 KB Output is correct
18 Correct 578 ms 68432 KB Output is correct
19 Correct 237 ms 44480 KB Output is correct
20 Correct 670 ms 81492 KB Output is correct
21 Correct 567 ms 68692 KB Output is correct
22 Correct 1708 ms 217156 KB Output is correct
23 Correct 1786 ms 217356 KB Output is correct
24 Correct 2550 ms 291384 KB Output is correct
25 Correct 2857 ms 296844 KB Output is correct
26 Correct 2613 ms 292032 KB Output is correct
27 Correct 3249 ms 374168 KB Output is correct
28 Correct 630 ms 116908 KB Output is correct
29 Correct 2660 ms 293204 KB Output is correct
30 Correct 2603 ms 290608 KB Output is correct
31 Correct 3392 ms 295696 KB Output is correct
32 Correct 1139 ms 87184 KB Output is correct
33 Correct 290 ms 44460 KB Output is correct
34 Correct 590 ms 58832 KB Output is correct
35 Correct 554 ms 66052 KB Output is correct
36 Correct 682 ms 71248 KB Output is correct
37 Correct 667 ms 71296 KB Output is correct