Submission #900094

#	Time	Username	Problem	Language	Result	Execution time	Memory
900094		yellowtoad	Factories (JOI14_factories)	C++17	100 / 100	5285 ms	237860 KiB

factories

#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
 
long long n, dist[500010], depth[500010], ord[500010], p[500010][20], cnt, dp[500010], node[500010], par[500010], lst, minn;
vector<pair<long long,long long>> edge[500010], nodes, stack;
vector<int> stk, hv, adj[500010];
 
void dfs1(int u, int v, long long _dist, int _depth) {
    dist[u] = _dist;
    depth[u] = _depth;
    p[u][0] = v;
    ord[u] = ++cnt;
    for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
    for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs1(edge[u][i].f,u,_dist+edge[u][i].s,_depth+1);
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n-1; i++) {
        edge[A[i]+1].push_back({B[i]+1,D[i]});
        edge[B[i]+1].push_back({A[i]+1,D[i]});
    }
    for (int i = 0; i <= n; i++) dp[i] = 1e18;
    dfs1(1,0,0,1);
}
 
int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u,v);
    int i = 19;
    while (i >= 0) {
        if (depth[p[v][i]] >= depth[u]) v = p[v][i];
        i--;
    }
    if (u == v) return u;
    i = 19;
    while (i >= 0) {
        if (p[v][i] != p[u][i]) v = p[v][i], u = p[u][i];
        i--;
    }
    return p[u][0];
}
 
void dfs2(int u) {
    if (node[u] == 1) dp[u] = dist[u];
    for (int i = 0; i < adj[u].size(); i++) {
        dfs2(adj[u][i]);
        dp[u] = min(dp[u],dp[adj[u][i]]);
    }
}
 
void dfs3(int u) {
    if (dp[u] != 1e18) dp[u] = (long long)1e17+dp[u]-2*dist[u];
    for (int i = 0; i < adj[u].size(); i++) dfs3(adj[u][i]);
}
 
void dfs4(int u) {
    if (node[u] == 2) minn = min(minn,stack.back().f-(long long)1e17+dist[u]);
    for (int i = 0; i < adj[u].size(); i++) {
        if (stack.back().f >= dp[adj[u][i]]) stack.push_back({dp[adj[u][i]],adj[u][i]});
        else stack.push_back(stack.back());
        dfs4(adj[u][i]);
        stack.pop_back();
    }
}
 
long long Query(int S, int X[], int T, int Y[]) {
    minn = 1e18;
    for (int i = 0; i < S; i++) {
        node[X[i]+1] = 1;
        nodes.push_back({ord[X[i]+1],X[i]+1});
    }
    for (int i = 0; i < T; i++) {
        node[Y[i]+1] = 2;
        nodes.push_back({ord[Y[i]+1],Y[i]+1});
    }
    sort(nodes.begin(),nodes.end());
    for (int i = 0; i < nodes.size(); i++) {
        if (stk.size()) {
            int u = lca(nodes[i].s,stk.back());
            while (stk.size() && (lca(u,stk.back()) == u)) {
                lst = stk.back();
                hv.push_back(lst);
                stk.pop_back();
                if (stk.size()) par[lst] = stk.back();
            }
            if (lst == u) hv.pop_back();
            else par[lst] = u;
            stk.push_back(u);
        } 
        stk.push_back(nodes[i].s);
    }
    while (stk.size()) {
        lst = stk.back();
        stk.pop_back();
        hv.push_back(lst);
        if (stk.size()) par[lst] = stk.back();
    }
    for (int i = 0; i < hv.size(); i++) adj[par[hv[i]]].push_back(hv[i]);
    dfs2(0);
    dfs3(0);
    stack.push_back({dp[0],0});
    dfs4(0);
    for (int i = 0; i < S; i++) node[X[i]+1] = 0;
    for (int i = 0; i < T; i++) node[Y[i]+1] = 0;
    for (int i = 0; i < hv.size(); i++) dp[hv[i]] = 1e18, par[hv[i]] = 0, adj[hv[i]].clear();
    adj[0].clear();
    dp[0] = 1e18;
    nodes.clear();
    hv.clear();
    stk.clear();
    stack.clear();
    return minn;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs1(int, int, long long int, int)':
factories.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs1(edge[u][i].f,u,_dist+edge[u][i].s,_depth+1);
      |                     ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int)':
factories.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs3(int)':
factories.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < adj[u].size(); i++) dfs3(adj[u][i]);
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs4(int)':
factories.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < nodes.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
factories.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 0; i < hv.size(); i++) adj[par[hv[i]]].push_back(hv[i]);
      |                     ~~^~~~~~~~~~~
factories.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < hv.size(); i++) dp[hv[i]] = 1e18, par[hv[i]] = 0, adj[hv[i]].clear();
      |                     ~~^~~~~~~~~~~

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