Submission #390703

#	Time	Username	Problem	Language	Result	Execution time	Memory
390703		ritul_kr_singh	Factories (JOI14_factories)	C++17	100 / 100	5280 ms	191720 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67