oj.uz

답안 #807167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807167 2023-08-04T14:22:05 Z hoangnghiep 공장들 (JOI14_factories) C++14
15 / 100
 2608 ms 23052 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]){
			if(dist[v.f]==-1) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1408 KB Output is correct
2 Correct 2420 ms 11852 KB Output is correct
3 Correct 2453 ms 11812 KB Output is correct
4 Correct 2365 ms 11844 KB Output is correct
5 Correct 1410 ms 12212 KB Output is correct
6 Correct 2608 ms 12048 KB Output is correct
7 Correct 2344 ms 11928 KB Output is correct
8 Correct 1874 ms 12120 KB Output is correct
9 Correct 1334 ms 12332 KB Output is correct
10 Correct 2581 ms 12184 KB Output is correct
11 Correct 2343 ms 11936 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1232 KB Output is correct
2 Runtime error 220 ms 23052 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1408 KB Output is correct
2 Correct 2420 ms 11852 KB Output is correct
3 Correct 2453 ms 11812 KB Output is correct
4 Correct 2365 ms 11844 KB Output is correct
5 Correct 1410 ms 12212 KB Output is correct
6 Correct 2608 ms 12048 KB Output is correct
7 Correct 2344 ms 11928 KB Output is correct
8 Correct 1874 ms 12120 KB Output is correct
9 Correct 1334 ms 12332 KB Output is correct
10 Correct 2581 ms 12184 KB Output is correct
11 Correct 2343 ms 11936 KB Output is correct
12 Correct 17 ms 1232 KB Output is correct
13 Runtime error 220 ms 23052 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -