oj.uz

Submission #422403

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

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

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 75 ms 12444 KB Output is correct
2 Correct 6585 ms 21072 KB Output is correct
3 Correct 6485 ms 21116 KB Output is correct
4 Correct 5422 ms 21132 KB Output is correct
5 Correct 3826 ms 21320 KB Output is correct
6 Correct 7103 ms 21252 KB Output is correct
7 Correct 6248 ms 20980 KB Output is correct
8 Correct 5618 ms 21224 KB Output is correct
9 Correct 3736 ms 21304 KB Output is correct
10 Correct 6990 ms 21296 KB Output is correct
11 Correct 6289 ms 20892 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12236 KB Output is correct
2 Correct 1493 ms 92464 KB Output is correct
3 Correct 4301 ms 93996 KB Output is correct
4 Correct 1222 ms 93168 KB Output is correct
5 Correct 1539 ms 116572 KB Output is correct
6 Correct 2871 ms 95508 KB Output is correct
7 Execution timed out 8071 ms 37196 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12444 KB Output is correct
2 Correct 6585 ms 21072 KB Output is correct
3 Correct 6485 ms 21116 KB Output is correct
4 Correct 5422 ms 21132 KB Output is correct
5 Correct 3826 ms 21320 KB Output is correct
6 Correct 7103 ms 21252 KB Output is correct
7 Correct 6248 ms 20980 KB Output is correct
8 Correct 5618 ms 21224 KB Output is correct
9 Correct 3736 ms 21304 KB Output is correct
10 Correct 6990 ms 21296 KB Output is correct
11 Correct 6289 ms 20892 KB Output is correct
12 Correct 12 ms 12236 KB Output is correct
13 Correct 1493 ms 92464 KB Output is correct
14 Correct 4301 ms 93996 KB Output is correct
15 Correct 1222 ms 93168 KB Output is correct
16 Correct 1539 ms 116572 KB Output is correct
17 Correct 2871 ms 95508 KB Output is correct
18 Execution timed out 8071 ms 37196 KB Time limit exceeded
19 Halted 0 ms 0 KB -