Submission #425698

#	Time	Username	Problem	Language	Result	Execution time	Memory
425698		tht2005	Factories (JOI14_factories)	C++14	15 / 100	1833 ms	242240 KiB

factories

/*
 *  Written by
 *       ______  _   _  ______  ____  ____  ____  ____
 *      |_    _|| |_| ||_    _||_   || __ || __ |/  _/
 *        |  |  |  _  |  |  |    / / ||  ||||  ||| |__
 *        |  |  | | | |  |  |   | |_ ||__||||__||\__  \
 *        |__|  |_| |_|  |__|   |___||____||____|/____/
 */

//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define nmax 500005
#define ll long long
#define ii pair<int, int>

const ll inf = (ll)1e15;
int n, sz[nmax], p[nmax], r[nmax], depth[nmax], rmq[nmax][21], ln[nmax<<2], pos[nmax], euler[nmax<<2], ea;
ll ans[nmax], sum[nmax];
vector<ii> adj[nmax];

int dfs(int u, int p = -1)
{
    sz[u] = 1;
    for(auto [C, v]: adj[u]) {
        if(v != p && !r[v]) sz[u] += dfs(v, u);
    }
    return sz[u];
}

int find_centroid(int m, int u, int p = -1)
{
    for(auto [C, v]: adj[u]) {
        if(v != p && !r[v] && 2 * sz[v] > m)
            return find_centroid(m, v, u);
    }
    return u;
}

int centroid(int u = 0)
{
    u = find_centroid(dfs(u), u);
    r[u] = 1;
    p[u] = -1;
    for(auto [C, v]: adj[u]) {
        if(!r[v]) p[centroid(v)] = u;
    }
    return u;
}

void dfs2(int u, int p = -1)
{
    pos[u] = ea;
    euler[ea++] = u;
    for(auto [C, v]: adj[u]) {
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        sum[v] = sum[u] + C;
        dfs2(v, u);
        euler[ea++] = u;
    }
}

int lca(int x, int y)
{
    x = pos[x];
    y = pos[y];
    if(x > y) swap(x, y);
    int j = ln[y - x + 1];
    return depth[euler[rmq[x][j]]] < depth[euler[rmq[y - (1 << j) + 1][j]]] ? euler[rmq[x][j]] : euler[rmq[y - (1 << j) + 1][j]];
}

inline ll dist(int x, int y)
{
    return sum[x] + sum[y] - 2 * sum[lca(x, y)];
}

void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i < n - 1; ++i) {
        adj[A[i]].push_back(ii(D[i], B[i]));
        adj[B[i]].push_back(ii(D[i], A[i]));
    }
    centroid();
    fill(ans, ans + n, inf);
    sum[0] = depth[0] = 0;
    dfs2(0);
    ln[1] = 0;
    for(int i = 2; i < ea + 1; ++i) {
        ln[i] = ln[i >> 1] + 1;
    }
    for(int i = 0; i < ea; ++i)
        rmq[i][0] = i;
    for(int j = 1; j < 21; ++j) {
        for(int i = 0; i + (1 << j) - 1 < ea; ++i) {
            if(depth[euler[rmq[i][j - 1]]] < depth[euler[rmq[i + (1 << (j - 1))][j - 1]]])
                rmq[i][j] = rmq[i][j - 1];
            else
                rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
        }
    }
}

void update(int y, bool del)
{
    for(int x = y; x != -1; x = p[x]) {
        if(del) ans[x] = inf;
        else ans[x] = min(ans[x], dist(x, y));
    }
}

ll get(int y)
{
    ll res = inf;
    for(int x = y; x != -1; x = p[x])
        res = min(res, ans[x] + dist(x, y));
    return res;
}

ll Query(int S, int X[], int T, int Y[])
{
    ll res = inf;
    if(S <= 10 && T <= 10) {
        for(int i = 0; i < S; ++i) {
            for(int j = 0; j < T; ++j)
                res = min(res, dist(X[i], Y[j]));
        }
        return res;
    }
    for(int i = 0; i < S; ++i) {
        update(X[i], 0);
    }
    for(int i = 0; i < T; ++i) {
        res = min(res, get(Y[i]));
    }
    for(int i = 0; i < S; ++i) {
        update(X[i], 1);
    }
    return res;
}

Compilation message (stderr)

factories.cpp: In function 'int dfs(int, int)':
factories.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [C, v]: adj[u]) {
      |              ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [C, v]: adj[u]) {
      |              ^
factories.cpp: In function 'int centroid(int)':
factories.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for(auto [C, v]: adj[u]) {
      |              ^
factories.cpp: In function 'void dfs2(int, int)':
factories.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [C, v]: adj[u]) {
      |              ^

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67