Submission #1305068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305068		lsjo	Factories (JOI14_factories)	C++20	18 / 100	8090 ms	189572 KiB

factories

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

vector<pair<int,int>> graph[500005];
bool vis[500005];
int depth[500005], parent[500005], jump[500005][20];
long long dist[500005][20];

void dfs(int node) {
    vis[node]=true;

    for (auto x : graph[node]) {
        if (! vis[x.first]) {
            depth[x.first]=depth[node]+1;
            parent[x.first]=node;
            jump[x.first][0]=node;
            dist[x.first][0]=x.second;

            dfs(x.first);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
  for (int i = 0; i < N-1; i++) {
    graph[A[i]].push_back({B[i], D[i]});
    graph[B[i]].push_back({A[i], D[i]});
  }

  depth[0]=0;
  parent[0]=0;
  jump[0][0]=0;
  dist[0][0]=0;

  dfs(0);

  for (int j = 1; j <= 19; j++) {
    for (int i = 0; i < N; i++) {
        jump[i][j]=jump[jump[i][j-1]][j-1];
        dist[i][j]=dist[i][j-1]+dist[jump[i][j-1]][j-1];
        //cout << dist[i][0] << " ";
    }
    //cout << "\n";
  }
}

long long Query(int S, int X[], int T, int Y[]) {
    long long mindist=1e18;
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < T; j++) {
            int u=X[i], v=Y[j];
            long long d=0;

            if (depth[u] < depth[v]) swap(u, v);

            for (int i = 19; i >= 0; i--) {
                if (depth[jump[u][i]] >= depth[v]) {
                    d += dist[u][i];
                    u = jump[u][i];
                }
            }

            if (u != v) {
                for (int i = 19; i >= 0; i--) {
                    if (jump[u][i] != jump[v][i]) {
                        d += dist[u][i];
                        d += dist[v][i];
                        u=jump[u][i];
                        v=jump[v][i];
                    }
                }

                d += dist[u][0]+dist[v][0];
            }

            mindist=min(mindist, d);
        }
    }

    return mindist;
}

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