Submission #993813

#	Time	Username	Problem	Language	Result	Execution time	Memory
993813		Peti	Factories (JOI14_factories)	C++14	100 / 100	3392 ms	374168 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67