oj.uz

Submission #387976

# Submission time Handle Problem Language Result Execution time Memory
387976 2021-04-09T15:39:57 Z ritul_kr_singh Factories (JOI14_factories) C++17
100 / 100
 7102 ms 173004 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second
#include "factories.h"

const int MAXN = 5e5;
const ll INF = 1e18;

vector<vector<pair<int, ll>>> g(MAXN);
vector<vector<ll>> dist(20, vector<ll> (MAXN));
vector<int> s(MAXN), depth(MAXN), parent(MAXN);
vector<bool> r(MAXN);

vector<ll> ans(MAXN, INF);

int calcSize(int u, int p){
	s[u] = 1;
	for(auto &e : g[u]) if(v != p and !r[v]) s[u] += calcSize(v, u);
	return s[u];
}

void calcDist(int u, int p, ll currDist, int lvl){
	dist[lvl][u] = currDist;
	for(auto &e : g[u]) if(v != p and !r[v]) calcDist(v, u, currDist + w, lvl);
}

int find(int u, int p, int treeSize){
	for(auto &e : g[u]) if(v != p and !r[v] and s[v] > treeSize/2) return find(v, u, treeSize);
	return u; 
}

int decompose(int u, int lvl){
	int c = find(u, u, calcSize(u, u));
	calcDist(c, c, 0, lvl);
	r[c] = true, depth[c] = lvl++;
	for(auto &e : g[c]) if(!r[v]) parent[decompose(v, lvl)] = c;
	return c;
}

void build(int u, int source){
	ans[u] = min(ans[u], dist[depth[u]][source]);
	if(depth[u]) build(parent[u], source);
}

void reset(int u){
	ans[u] = INF;
	if(depth[u]) reset(parent[u]);
}

ll get(int u, int source){
	if(!depth[u]) return ans[u] + dist[depth[u]][source];
	else return min(ans[u] + dist[depth[u]][source], get(parent[u], source));
}

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

ll Query(int S, int X[], int T, int Y[]){
	for(int i=0; i<S; ++i) build(X[i], X[i]);
	ll res = INF;
	for(int i=0; i<T; ++i) res = min(res, get(Y[i], Y[i]));
	for(int i=0; i<S; ++i) reset(X[i]);
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 100480 KB Output is correct
2 Correct 447 ms 108536 KB Output is correct
3 Correct 507 ms 108512 KB Output is correct
4 Correct 523 ms 108664 KB Output is correct
5 Correct 538 ms 108876 KB Output is correct
6 Correct 329 ms 108668 KB Output is correct
7 Correct 494 ms 108520 KB Output is correct
8 Correct 503 ms 108548 KB Output is correct
9 Correct 537 ms 108992 KB Output is correct
10 Correct 335 ms 108424 KB Output is correct
11 Correct 492 ms 108604 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 100324 KB Output is correct
2 Correct 2966 ms 138864 KB Output is correct
3 Correct 4280 ms 142452 KB Output is correct
4 Correct 1008 ms 136360 KB Output is correct
5 Correct 6072 ms 173004 KB Output is correct
6 Correct 4845 ms 143744 KB Output is correct
7 Correct 1729 ms 116800 KB Output is correct
8 Correct 496 ms 116324 KB Output is correct
9 Correct 1964 ms 121348 KB Output is correct
10 Correct 1600 ms 117968 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 100480 KB Output is correct
2 Correct 447 ms 108536 KB Output is correct
3 Correct 507 ms 108512 KB Output is correct
4 Correct 523 ms 108664 KB Output is correct
5 Correct 538 ms 108876 KB Output is correct
6 Correct 329 ms 108668 KB Output is correct
7 Correct 494 ms 108520 KB Output is correct
8 Correct 503 ms 108548 KB Output is correct
9 Correct 537 ms 108992 KB Output is correct
10 Correct 335 ms 108424 KB Output is correct
11 Correct 492 ms 108604 KB Output is correct
12 Correct 55 ms 100324 KB Output is correct
13 Correct 2966 ms 138864 KB Output is correct
14 Correct 4280 ms 142452 KB Output is correct
15 Correct 1008 ms 136360 KB Output is correct
16 Correct 6072 ms 173004 KB Output is correct
17 Correct 4845 ms 143744 KB Output is correct
18 Correct 1729 ms 116800 KB Output is correct
19 Correct 496 ms 116324 KB Output is correct
20 Correct 1964 ms 121348 KB Output is correct
21 Correct 1600 ms 117968 KB Output is correct
22 Correct 3541 ms 140300 KB Output is correct
23 Correct 3790 ms 142772 KB Output is correct
24 Correct 5677 ms 144232 KB Output is correct
25 Correct 5646 ms 147800 KB Output is correct
26 Correct 5667 ms 144452 KB Output is correct
27 Correct 7102 ms 169736 KB Output is correct
28 Correct 1194 ms 140284 KB Output is correct
29 Correct 5392 ms 144068 KB Output is correct
30 Correct 6091 ms 143360 KB Output is correct
31 Correct 5747 ms 144196 KB Output is correct
32 Correct 1985 ms 122320 KB Output is correct
33 Correct 484 ms 116732 KB Output is correct
34 Correct 1202 ms 114440 KB Output is correct
35 Correct 1208 ms 114416 KB Output is correct
36 Correct 1626 ms 115328 KB Output is correct
37 Correct 1671 ms 115440 KB Output is correct