oj.uz

Submission #958769

# Submission time Handle Problem Language Result Execution time Memory
958769 2024-04-06T14:57:50 Z pcc Factories (JOI14_factories) C++17
100 / 100
 5325 ms 189792 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

const int mxn = 5e5+10;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second

namespace TREE{
	vector<pii> tree[mxn];
	int dfn[mxn],dep[mxn],par[mxn][20],pt = 0;
	ll dp[mxn];
	void dfs(int now){
		dfn[now] = pt++;
		for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
		for(auto nxt:tree[now]){
			if(nxt.fs == par[now][0])continue;
			dep[nxt.fs] = dep[now]+1;
			dp[nxt.fs] = dp[now]+nxt.sc;
			par[nxt.fs][0] = now;
			dfs(nxt.fs);
		}
	}
	int LCA(int a,int b){
		if(dep[a]<dep[b])swap(a,b);
		int d = dep[a]-dep[b];
		for(int i = 19;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		for(int i = 19;i>=0;i--){
			if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
		}
		return a == b?a:par[a][0];
	}
	ll dist(int a,int b){
		return dp[a]+dp[b]-dp[LCA(a,b)]*2;
	}
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0;i<N-1;i++){
		int a = A[i],b = B[i],w = D[i];
		TREE::tree[a].push_back(pii(b,w));
		TREE::tree[b].push_back(pii(a,w));
	}
	TREE::par[0][0] = 0;
	TREE::dfs(0);
}

namespace PEKO{
	vector<pll> tree[mxn];
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	vector<int> tv;
	ll dist[mxn];
	void init(){
		for(auto &i:tv){
			dist[i] = 1e18;
			tree[i].clear();
		}
		tv.clear();
	}
	void GO(vector<int> &v){
		init();
		sort(v.begin(),v.end(),[](int a,int b){return TREE::dfn[a]<TREE::dfn[b];});
		int s = v.size();
		for(int i = 1;i<s;i++)v.push_back(TREE::LCA(v[i-1],v[i]));
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		sort(v.begin(),v.end(),[](int a,int b){return TREE::dfn[a]<TREE::dfn[b];});
		tv = v;
		for(int i = 1;i<v.size();i++){
			int a = TREE::LCA(v[i-1],v[i]);
			int b = v[i];
			ll d = TREE::dist(a,b);
			tree[a].push_back(pll(b,d));
			tree[b].push_back(pll(a,d));
		}
		return;
	}
	void DIJKSTRA(vector<int> &st){
		for(auto &i:tv)dist[i] = 1e18;
		for(auto &i:st){
			dist[i] = 0;
			pq.push(pll(dist[i],i));
		}
		while(!pq.empty()){
			auto [d,now] = pq.top();
			pq.pop();
			if(dist[now] != d)continue;
			for(auto [nxt,w]:tree[now]){
				if(dist[nxt]>d+w){
					dist[nxt] = d+w;
					pq.push(pll(dist[nxt],nxt));
				}
			}
		}
		return;
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> v;
	for(int i = 0;i<S;i++)v.push_back(X[i]);
	for(int i = 0;i<T;i++)v.push_back(Y[i]);
	v.push_back(0);
	PEKO::GO(v);
	v.clear();
	for(int i = 0;i<S;i++)v.push_back(X[i]);
	PEKO::DIJKSTRA(v);
	ll ans = 1e18;
	for(int i = 0;i<T;i++)ans = min(ans,PEKO::dist[Y[i]]);
	return ans;
}

Compilation message

factories.cpp: In function 'void PEKO::GO(std::vector<int>&)':
factories.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i = 1;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 49940 KB Output is correct
2 Correct 1569 ms 64096 KB Output is correct
3 Correct 1736 ms 63800 KB Output is correct
4 Correct 1561 ms 64020 KB Output is correct
5 Correct 1338 ms 64640 KB Output is correct
6 Correct 1202 ms 63824 KB Output is correct
7 Correct 1759 ms 63796 KB Output is correct
8 Correct 1609 ms 63944 KB Output is correct
9 Correct 1326 ms 64336 KB Output is correct
10 Correct 1211 ms 64016 KB Output is correct
11 Correct 1719 ms 64020 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 49756 KB Output is correct
2 Correct 2032 ms 147572 KB Output is correct
3 Correct 2735 ms 151380 KB Output is correct
4 Correct 1527 ms 147468 KB Output is correct
5 Correct 2683 ms 184572 KB Output is correct
6 Correct 2892 ms 152860 KB Output is correct
7 Correct 2602 ms 87172 KB Output is correct
8 Correct 1361 ms 86364 KB Output is correct
9 Correct 1872 ms 92104 KB Output is correct
10 Correct 2464 ms 87628 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 49940 KB Output is correct
2 Correct 1569 ms 64096 KB Output is correct
3 Correct 1736 ms 63800 KB Output is correct
4 Correct 1561 ms 64020 KB Output is correct
5 Correct 1338 ms 64640 KB Output is correct
6 Correct 1202 ms 63824 KB Output is correct
7 Correct 1759 ms 63796 KB Output is correct
8 Correct 1609 ms 63944 KB Output is correct
9 Correct 1326 ms 64336 KB Output is correct
10 Correct 1211 ms 64016 KB Output is correct
11 Correct 1719 ms 64020 KB Output is correct
12 Correct 13 ms 49756 KB Output is correct
13 Correct 2032 ms 147572 KB Output is correct
14 Correct 2735 ms 151380 KB Output is correct
15 Correct 1527 ms 147468 KB Output is correct
16 Correct 2683 ms 184572 KB Output is correct
17 Correct 2892 ms 152860 KB Output is correct
18 Correct 2602 ms 87172 KB Output is correct
19 Correct 1361 ms 86364 KB Output is correct
20 Correct 1872 ms 92104 KB Output is correct
21 Correct 2464 ms 87628 KB Output is correct
22 Correct 4666 ms 162572 KB Output is correct
23 Correct 3965 ms 162652 KB Output is correct
24 Correct 5151 ms 166784 KB Output is correct
25 Correct 5007 ms 168460 KB Output is correct
26 Correct 5325 ms 160544 KB Output is correct
27 Correct 4206 ms 189792 KB Output is correct
28 Correct 2979 ms 159460 KB Output is correct
29 Correct 5175 ms 159228 KB Output is correct
30 Correct 5104 ms 158408 KB Output is correct
31 Correct 5285 ms 158916 KB Output is correct
32 Correct 2108 ms 95044 KB Output is correct
33 Correct 1915 ms 90788 KB Output is correct
34 Correct 2495 ms 86620 KB Output is correct
35 Correct 2531 ms 86880 KB Output is correct
36 Correct 2916 ms 87892 KB Output is correct
37 Correct 3068 ms 87468 KB Output is correct