Submission #422403

#	Time	Username	Problem	Language	Result	Execution time	Memory
422403		milleniumEeee	Factories (JOI14_factories)	C++11	15 / 100	8071 ms	116572 KiB

factories

#include "factories.h"
#ifndef EVAL  
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXN = (int)5e5 + 5;
const int MAXQ = (int)1e5 + 5;
const int L = 20;

vector <pii> g[MAXN];
int n;

int pr[MAXN][L + 1];
ll d[MAXN];
int tin[MAXN], tout[MAXN], tiktak;

void precalc(int v, int par, ll len) {
	tin[v] = ++tiktak;
	pr[v][0] = par;
	d[v] = len;
	for (int lv = 1; lv <= L; lv++) {
		pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
	}
	for (auto [to, dist] : g[v]) {
		if (to == par) {
			continue;
		}
		precalc(to, v, len + dist);
	}
	tout[v] = tiktak;
}

bool father(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int get_lca(int a, int b) {
	if (father(a, b)) {
		return a;
	}
	if (father(b, a)) {
		return b;
	}
	for (int lv = L; lv >= 0; lv--) {
		if (!father(pr[a][lv], b)) {
			a = pr[a][lv];
		}
	}
	return pr[a][0];
}

ll get_dist(int a, int b) {
	return d[a] + d[b] - (2ll * d[get_lca(a, b)]);
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		int u = A[i];
		int v = B[i];
		int dist = D[i];
		g[u].pb({v, dist});
		g[v].pb({u, dist});
	}
	precalc(0, 0, 0);
}

ll dist[3][MAXN];

void dijkstra(vector <int> start, ll *min_dist) {
	fill(min_dist, min_dist + n + 123, -1);
	priority_queue <pair<ll, int>> pq;
	for (int el : start) {
		min_dist[el] = 0;
		pq.push({0, el});
	}
	while (!pq.empty()) {
		ll cost = -pq.top().fr;
		int v = pq.top().sc;
		pq.pop();
		if (cost > min_dist[v]) {
			continue;
		}
		for (auto [to, dist] : g[v]) {
			if (min_dist[to] == -1 || min_dist[to] > cost + dist) {
				min_dist[to] = cost + dist;
				pq.push({-min_dist[to], to});
			}
		}
	}
}

bool ok = 1;

ll Query(int S, int X[], int T, int Y[]) {
	if (!ok) {
		vector <int> start_s, start_t;
		for (int i = 0; i < S; i++) {
			start_s.pb(X[i]);
		}
		for (int i = 0; i < T; i++) {
			start_t.pb(Y[i]);
		}
		dijkstra(start_s, dist[1]);
		dijkstra(start_t, dist[2]);
		ll ans = INF;
		for (int i = 0; i < n; i++) {
			ans = min(ans, dist[1][i] + dist[2][i]);
		}	
		return ans;
	}
	ok &= (S <= 10 && T <= 10);
	if (ok) {
		ll ans = INF;
		for (int i = 0; i < S; i++) {
			for (int j = 0; j < T; j++) {
				ans = min(ans, get_dist(X[i], Y[j]));
			}
		}
		return ans;
	} 
	else {
		vector <int> start_s, start_t;
		for (int i = 0; i < S; i++) {
			start_s.pb(X[i]);
		}
		for (int i = 0; i < T; i++) {
			start_t.pb(Y[i]);
		}
		dijkstra(start_s, dist[1]);
		dijkstra(start_t, dist[2]);
		ll ans = INF;
		for (int i = 0; i < n; i++) {
			ans = min(ans, dist[1][i] + dist[2][i]);
		}	
		return ans;		
	}
}

Compilation message (stderr)

factories.cpp: In function 'void precalc(int, int, long long int)':
factories.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  for (auto [to, dist] : g[v]) {
      |            ^
factories.cpp: In function 'void dijkstra(std::vector<int>, long long int*)':
factories.cpp:96:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for (auto [to, dist] : g[v]) {
      |             ^

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