oj.uz

Submission #422401

# Submission time Handle Problem Language Result Execution time Memory
422401 2021-06-10T05:45:09 Z milleniumEeee Factories (JOI14_factories) C++11
15 / 100
 8000 ms 116540 KB 
#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});
			}
		}
	}
}

ll Query(int S, int X[], int T, int Y[]) {
	if (max(S, T) <= 10) {
		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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 12620 KB Output is correct
2 Correct 2107 ms 23088 KB Output is correct
3 Correct 6171 ms 21904 KB Output is correct
4 Correct 4415 ms 22184 KB Output is correct
5 Correct 1891 ms 22192 KB Output is correct
6 Correct 2029 ms 22140 KB Output is correct
7 Correct 6176 ms 21844 KB Output is correct
8 Correct 4500 ms 21136 KB Output is correct
9 Correct 1915 ms 21336 KB Output is correct
10 Correct 2043 ms 21208 KB Output is correct
11 Correct 6262 ms 20932 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12236 KB Output is correct
2 Correct 1448 ms 92552 KB Output is correct
3 Correct 3784 ms 94268 KB Output is correct
4 Correct 1125 ms 93172 KB Output is correct
5 Correct 1529 ms 116540 KB Output is correct
6 Correct 2926 ms 95360 KB Output is correct
7 Execution timed out 8052 ms 37204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 12620 KB Output is correct
2 Correct 2107 ms 23088 KB Output is correct
3 Correct 6171 ms 21904 KB Output is correct
4 Correct 4415 ms 22184 KB Output is correct
5 Correct 1891 ms 22192 KB Output is correct
6 Correct 2029 ms 22140 KB Output is correct
7 Correct 6176 ms 21844 KB Output is correct
8 Correct 4500 ms 21136 KB Output is correct
9 Correct 1915 ms 21336 KB Output is correct
10 Correct 2043 ms 21208 KB Output is correct
11 Correct 6262 ms 20932 KB Output is correct
12 Correct 10 ms 12236 KB Output is correct
13 Correct 1448 ms 92552 KB Output is correct
14 Correct 3784 ms 94268 KB Output is correct
15 Correct 1125 ms 93172 KB Output is correct
16 Correct 1529 ms 116540 KB Output is correct
17 Correct 2926 ms 95360 KB Output is correct
18 Execution timed out 8052 ms 37204 KB Time limit exceeded
19 Halted 0 ms 0 KB -