oj.uz

Submission #807107

# Submission time Handle Problem Language Result Execution time Memory
807107 2023-08-04T13:18:44 Z hoangnghiep Factories (JOI14_factories) C++14
15 / 100
 4940 ms 23148 KB 
#include<bits/stdc++.h>
#include "factories.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define f first
#define s second
#define pii pair<ll,ll>
#define piii pair<ll,pair<ll,ll>>
#define vii vector<vector<ll>>
#define vi vector<ll>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const ll LIM=5000;
const string name="template";
ll n,m;
vector<pii> adj[LIM+5],adj_vt[LIM+5];
ll time_dfs=0;
pii euler_tour[1000005],sparse_table[20][LIM+5];
ll dist[LIM+5];
ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[20][LIM+5];
vector<ll> List;
 
priority_queue<pii,vector<pii>,greater<pii>> pq;
 
void dfs(ll u,ll parent,ll depth){
 
	h[u] = depth;
	
	tin[u] = time_dfs;
	
	euler_tour[time_dfs++] = {depth,u};
	
	low[0][u] = parent;
	 
	for(auto v:adj[u]){
		if(v.f==parent) continue;
		dfs(v.f,u,depth + 1);
		
		euler_tour[time_dfs++] = {depth,u};
		
		up_weight[0][v.f] = v.s;	
	}
	tout[u] = time_dfs;
}
 
ll lca(ll u,ll v){
	if(tin[u]>tin[v]){
		swap(u,v);
	}
	ll bt = 63 - __builtin_clzll(tin[v]-tin[u]+1);
	pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
	return mn.s;
}
 
ll lift_weight(ll u,ll k){
	ll tmp=0;
	ll w = 0;
	while(k>0){
		if(k%2==1){
			w+=up_weight[tmp][u];
			u=low[tmp][u];
		}
		k>>=1;
		tmp++;
	}
	return w;
}
 
bool cmp(ll a,ll b){
	return tin[a]<tin[b];
}
 
ll isSubtree(ll u,ll v)
{
	return tin[u]<=tin[v] && tin[v]<=tout[u];
}
 
void Init(int N, int A[], int B[], int D[]){
	n=N;
	time_dfs=0;
	for(ll i=0;i<n-1;++i){
		A[i]++;
		B[i]++;
	}
	for(ll i=0;i<n-1;++i){
		adj[A[i]].push_back({B[i],D[i]});
		adj[B[i]].push_back({A[i],D[i]});
	}
	for(ll i=1;i<=n;++i){
		dist[i]=-1;
	}
	
	dfs(1,0,0);
	
	for(ll i=0;i<time_dfs;++i){
		sparse_table[0][i]  = euler_tour[i];
	}
	
 	for(ll i=1;i<20;++i){
		for(ll j=0;j+(1<<i)-1<time_dfs;++j){
			sparse_table[i][j] = min(sparse_table[i-1][j],sparse_table[i-1][j + (1<<(i-1))]);
		}
	}
	
	for(ll i=1;i<20;++i){
		for(ll j=1;j<=n;++j){
			low[i][j] =low[i-1][low[i-1][j]];
			up_weight[i][j] = up_weight[i-1][j] + up_weight[i-1][low[i-1][j]];
		}
	}
	
}
 
long long Query(int S, int X[], int T, int Y[])
{
	for(int i=0;i<T;++i){
		pq.push({0,++Y[i]});
	}
	while(!pq.empty()){
		ll u = pq.top().s;
		ll w= pq.top().f;
		pq.pop();
		if(dist[u]!=-1) continue;
		dist[u] = w;
		for(auto v:adj[u]){
			pq.push({w + v.s,v.f});
		}
	}
	long long ans=LLONG_MAX;
	for(ll i=0;i<S;++i){
		ans = min(ans,dist[++X[i]]);
	}
	for(int i=1;i<=n;++i){
		dist[i]=-1;
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1420 KB Output is correct
2 Correct 4736 ms 11872 KB Output is correct
3 Correct 4270 ms 21300 KB Output is correct
4 Correct 4075 ms 21300 KB Output is correct
5 Correct 2409 ms 21836 KB Output is correct
6 Correct 4940 ms 21492 KB Output is correct
7 Correct 4360 ms 21280 KB Output is correct
8 Correct 3226 ms 21664 KB Output is correct
9 Correct 2479 ms 21712 KB Output is correct
10 Correct 4746 ms 21448 KB Output is correct
11 Correct 4376 ms 21324 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1236 KB Output is correct
2 Runtime error 239 ms 23148 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1420 KB Output is correct
2 Correct 4736 ms 11872 KB Output is correct
3 Correct 4270 ms 21300 KB Output is correct
4 Correct 4075 ms 21300 KB Output is correct
5 Correct 2409 ms 21836 KB Output is correct
6 Correct 4940 ms 21492 KB Output is correct
7 Correct 4360 ms 21280 KB Output is correct
8 Correct 3226 ms 21664 KB Output is correct
9 Correct 2479 ms 21712 KB Output is correct
10 Correct 4746 ms 21448 KB Output is correct
11 Correct 4376 ms 21324 KB Output is correct
12 Correct 42 ms 1236 KB Output is correct
13 Runtime error 239 ms 23148 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -