oj.uz

Submission #390703

# Submission time Handle Problem Language Result Execution time Memory
390703 2021-04-16T15:55:38 Z ritul_kr_singh Factories (JOI14_factories) C++17
100 / 100
 5280 ms 191720 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){
	if(u != p){
		s[p] -= s[u];
		s[u] += s[p];
	}
	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, s[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]);
	}
	calcSize(0, 0);
	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 66 ms 100608 KB Output is correct
2 Correct 440 ms 117920 KB Output is correct
3 Correct 499 ms 118016 KB Output is correct
4 Correct 502 ms 117972 KB Output is correct
5 Correct 547 ms 118288 KB Output is correct
6 Correct 331 ms 117924 KB Output is correct
7 Correct 490 ms 117976 KB Output is correct
8 Correct 511 ms 117984 KB Output is correct
9 Correct 544 ms 118400 KB Output is correct
10 Correct 340 ms 117956 KB Output is correct
11 Correct 505 ms 118156 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 100352 KB Output is correct
2 Correct 2242 ms 139488 KB Output is correct
3 Correct 3121 ms 143404 KB Output is correct
4 Correct 857 ms 154612 KB Output is correct
5 Correct 4032 ms 191720 KB Output is correct
6 Correct 3289 ms 162412 KB Output is correct
7 Correct 1508 ms 130556 KB Output is correct
8 Correct 464 ms 130356 KB Output is correct
9 Correct 1755 ms 135264 KB Output is correct
10 Correct 1496 ms 132040 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 100608 KB Output is correct
2 Correct 440 ms 117920 KB Output is correct
3 Correct 499 ms 118016 KB Output is correct
4 Correct 502 ms 117972 KB Output is correct
5 Correct 547 ms 118288 KB Output is correct
6 Correct 331 ms 117924 KB Output is correct
7 Correct 490 ms 117976 KB Output is correct
8 Correct 511 ms 117984 KB Output is correct
9 Correct 544 ms 118400 KB Output is correct
10 Correct 340 ms 117956 KB Output is correct
11 Correct 505 ms 118156 KB Output is correct
12 Correct 59 ms 100352 KB Output is correct
13 Correct 2242 ms 139488 KB Output is correct
14 Correct 3121 ms 143404 KB Output is correct
15 Correct 857 ms 154612 KB Output is correct
16 Correct 4032 ms 191720 KB Output is correct
17 Correct 3289 ms 162412 KB Output is correct
18 Correct 1508 ms 130556 KB Output is correct
19 Correct 464 ms 130356 KB Output is correct
20 Correct 1755 ms 135264 KB Output is correct
21 Correct 1496 ms 132040 KB Output is correct
22 Correct 3042 ms 164468 KB Output is correct
23 Correct 3035 ms 167148 KB Output is correct
24 Correct 4414 ms 168584 KB Output is correct
25 Correct 4382 ms 172432 KB Output is correct
26 Correct 4324 ms 151048 KB Output is correct
27 Correct 5280 ms 189752 KB Output is correct
28 Correct 1082 ms 141112 KB Output is correct
29 Correct 4306 ms 144780 KB Output is correct
30 Correct 4329 ms 144156 KB Output is correct
31 Correct 4329 ms 144808 KB Output is correct
32 Correct 1778 ms 135216 KB Output is correct
33 Correct 486 ms 129620 KB Output is correct
34 Correct 1058 ms 127316 KB Output is correct
35 Correct 1105 ms 127356 KB Output is correct
36 Correct 1505 ms 128028 KB Output is correct
37 Correct 1493 ms 128252 KB Output is correct