oj.uz

Submission #958772

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,sse4,avx2")
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:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 1;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47816 KB Output is correct
2 Correct 1222 ms 57600 KB Output is correct
3 Correct 1296 ms 57680 KB Output is correct
4 Correct 1194 ms 57788 KB Output is correct
5 Correct 1036 ms 57972 KB Output is correct
6 Correct 896 ms 57556 KB Output is correct
7 Correct 1285 ms 57804 KB Output is correct
8 Correct 1234 ms 57724 KB Output is correct
9 Correct 1034 ms 58164 KB Output is correct
10 Correct 906 ms 57680 KB Output is correct
11 Correct 1332 ms 57784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47704 KB Output is correct
2 Correct 1707 ms 140384 KB Output is correct
3 Correct 2402 ms 145944 KB Output is correct
4 Correct 1165 ms 140828 KB Output is correct
5 Correct 2525 ms 184212 KB Output is correct
6 Correct 2551 ms 146248 KB Output is correct
7 Correct 2086 ms 79904 KB Output is correct
8 Correct 1008 ms 78680 KB Output is correct
9 Correct 1667 ms 84656 KB Output is correct
10 Correct 1988 ms 80352 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47816 KB Output is correct
2 Correct 1222 ms 57600 KB Output is correct
3 Correct 1296 ms 57680 KB Output is correct
4 Correct 1194 ms 57788 KB Output is correct
5 Correct 1036 ms 57972 KB Output is correct
6 Correct 896 ms 57556 KB Output is correct
7 Correct 1285 ms 57804 KB Output is correct
8 Correct 1234 ms 57724 KB Output is correct
9 Correct 1034 ms 58164 KB Output is correct
10 Correct 906 ms 57680 KB Output is correct
11 Correct 1332 ms 57784 KB Output is correct
12 Correct 12 ms 47704 KB Output is correct
13 Correct 1707 ms 140384 KB Output is correct
14 Correct 2402 ms 145944 KB Output is correct
15 Correct 1165 ms 140828 KB Output is correct
16 Correct 2525 ms 184212 KB Output is correct
17 Correct 2551 ms 146248 KB Output is correct
18 Correct 2086 ms 79904 KB Output is correct
19 Correct 1008 ms 78680 KB Output is correct
20 Correct 1667 ms 84656 KB Output is correct
21 Correct 1988 ms 80352 KB Output is correct
22 Correct 3970 ms 152404 KB Output is correct
23 Correct 3375 ms 152492 KB Output is correct
24 Correct 4518 ms 157680 KB Output is correct
25 Correct 4344 ms 165964 KB Output is correct
26 Correct 4419 ms 157712 KB Output is correct
27 Correct 3770 ms 189432 KB Output is correct
28 Correct 2511 ms 155432 KB Output is correct
29 Correct 4413 ms 156284 KB Output is correct
30 Correct 4360 ms 155120 KB Output is correct
31 Correct 4304 ms 156188 KB Output is correct
32 Correct 1806 ms 91952 KB Output is correct
33 Correct 1479 ms 86692 KB Output is correct
34 Correct 1954 ms 82956 KB Output is correct
35 Correct 1942 ms 82608 KB Output is correct
36 Correct 2256 ms 83828 KB Output is correct
37 Correct 2303 ms 80116 KB Output is correct