oj.uz

Submission #372215

# Submission time Handle Problem Language Result Execution time Memory
372215 2021-02-27T09:25:46 Z MahdiBahramian Factories (JOI14_factories) C++11
100 / 100
 3977 ms 122700 KB 
#include "factories.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
const int Max = 5e5 + 10;
const int LOG = 20;
const ll INF = 1e17 + 10;
int n;
vector<pair<int , int>> N[Max];
int sttime[Max] , edtime[Max] , ttime , par[Max][LOG] , h[Max];
ll dst[Max];

void DFS(int v , int p = 0)
{
	sttime[v] = ++ttime;
	for(int lg = 1 ; lg < LOG ; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1];
	for(pair<int , int> u : N[v]) if(u.F != p) h[u.F] = h[v] + 1 , par[u.F][0] = v , dst[u.F] = dst[v] + u.S , DFS(u.F , v);
	edtime[v] = ttime + 1;
}
int lca(int a , int b)
{
	//if(a == b) return a;
	if(h[a] < h[b]) swap(a , b);
	for(int lg = LOG ; lg-- ; ) if((h[a] - h[b]) & (1 << lg)) a = par[a][lg];
	if(a == b) return a;
	for(int lg = LOG ; lg-- ; ) if(par[a][lg] != par[b][lg]) a = par[a][lg] , b = par[b][lg];
	return par[a][0];
}
void Init(int N , int A[] , int B[] , int D[])
{
	n = N;
	for(int i = 0 ; i < n - 1 ; i++) ::N[A[i]].pb(mp(B[i] , D[i])) , ::N[B[i]].pb(mp(A[i] , D[i]));
	DFS(0);
}

ll DST[Max] , S[Max];

void dfs(vector<int> verts)
{
	int R = 0; S[++R] = verts[0];
	for(int i = 1 ; i < verts.size() ; i++)
	{
		while(sttime[S[R]] > sttime[verts[i]] || edtime[S[R]] <= sttime[verts[i]])
		{
			DST[S[R]] = min(DST[S[R]] , DST[S[R - 1]] + dst[S[R]] - dst[S[R - 1]]);
			DST[S[R - 1]] = min(DST[S[R - 1]] , DST[S[R]] + dst[S[R]] - dst[S[R - 1]]);
			R--;
		}
		DST[S[R]] = min(DST[S[R]] , DST[verts[i]] + dst[verts[i]] - dst[S[R]]);
		DST[verts[i]] = min(DST[verts[i]] , DST[S[R]] + dst[verts[i]] - dst[S[R]]);
		S[++R] = verts[i];
	}
	while(R > 1)
	{
		DST[S[R]] = min(DST[S[R]] , DST[S[R - 1]] + dst[S[R]] - dst[S[R - 1]]);
		DST[S[R - 1]] = min(DST[S[R - 1]] , DST[S[R]] + dst[S[R]] - dst[S[R - 1]]);
		R--;
	}
}
long long Query(int S , int X[] , int T , int Y[])
{
	vector<pair<int , int>> srt1 , srt2;
	for(int i = 0 ; i < S ; i++) srt1.pb(mp(sttime[X[i]] , X[i])) , srt2.pb(mp(sttime[X[i]] , X[i]));
	for(int i = 0 ; i < T ; i++) srt1.pb(mp(sttime[Y[i]] , Y[i])) , srt2.pb(mp(sttime[Y[i]] , Y[i]));
	sort(srt1.begin() , srt1.end());

	for(int i = 0 ; i < srt1.size() - 1 ; i++)
	{
		int l = lca(srt1[i].S , srt1[i + 1].S);
		srt2.pb(mp(sttime[l] , l));
	}
	{
		int l = lca(srt1[0].S , srt1.back().S);
		srt2.pb(mp(sttime[l] , l));
	}
	sort(srt2.begin() , srt2.end());
	vector<int> verts;
	for(pair<int , int> v : srt2) verts.pb(v.S) , DST[v.S] = INF;
	verts.resize(unique(verts.begin() , verts.end()) - verts.begin());
	for(int i = 0 ; i < S ; i++) DST[X[i]] = 0;
	dfs(verts);
	dfs(verts);
	ll ans = INF;
	for(int i = 0 ; i < T ; i++) ans = min(ans , DST[Y[i]]);
	return ans;
}

Compilation message

factories.cpp: In function 'void dfs(std::vector<int>)':
factories.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 1 ; i < verts.size() ; i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0 ; i < srt1.size() - 1 ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12652 KB Output is correct
2 Correct 1002 ms 23212 KB Output is correct
3 Correct 1172 ms 23096 KB Output is correct
4 Correct 1008 ms 23452 KB Output is correct
5 Correct 859 ms 23492 KB Output is correct
6 Correct 797 ms 23408 KB Output is correct
7 Correct 1014 ms 23116 KB Output is correct
8 Correct 1004 ms 23288 KB Output is correct
9 Correct 887 ms 23508 KB Output is correct
10 Correct 857 ms 23320 KB Output is correct
11 Correct 967 ms 23092 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 1883 ms 96776 KB Output is correct
3 Correct 2751 ms 98140 KB Output is correct
4 Correct 1339 ms 97364 KB Output is correct
5 Correct 2973 ms 120696 KB Output is correct
6 Correct 2895 ms 99420 KB Output is correct
7 Correct 2224 ms 39824 KB Output is correct
8 Correct 1226 ms 40712 KB Output is correct
9 Correct 2288 ms 43372 KB Output is correct
10 Correct 2412 ms 41012 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12652 KB Output is correct
2 Correct 1002 ms 23212 KB Output is correct
3 Correct 1172 ms 23096 KB Output is correct
4 Correct 1008 ms 23452 KB Output is correct
5 Correct 859 ms 23492 KB Output is correct
6 Correct 797 ms 23408 KB Output is correct
7 Correct 1014 ms 23116 KB Output is correct
8 Correct 1004 ms 23288 KB Output is correct
9 Correct 887 ms 23508 KB Output is correct
10 Correct 857 ms 23320 KB Output is correct
11 Correct 967 ms 23092 KB Output is correct
12 Correct 11 ms 12396 KB Output is correct
13 Correct 1883 ms 96776 KB Output is correct
14 Correct 2751 ms 98140 KB Output is correct
15 Correct 1339 ms 97364 KB Output is correct
16 Correct 2973 ms 120696 KB Output is correct
17 Correct 2895 ms 99420 KB Output is correct
18 Correct 2224 ms 39824 KB Output is correct
19 Correct 1226 ms 40712 KB Output is correct
20 Correct 2288 ms 43372 KB Output is correct
21 Correct 2412 ms 41012 KB Output is correct
22 Correct 3040 ms 104664 KB Output is correct
23 Correct 2877 ms 105364 KB Output is correct
24 Correct 3207 ms 107096 KB Output is correct
25 Correct 3384 ms 107780 KB Output is correct
26 Correct 3709 ms 101260 KB Output is correct
27 Correct 3498 ms 122700 KB Output is correct
28 Correct 2164 ms 105132 KB Output is correct
29 Correct 3898 ms 100716 KB Output is correct
30 Correct 3944 ms 100192 KB Output is correct
31 Correct 3977 ms 100928 KB Output is correct
32 Correct 1926 ms 45580 KB Output is correct
33 Correct 1335 ms 42352 KB Output is correct
34 Correct 1754 ms 36580 KB Output is correct
35 Correct 1834 ms 36460 KB Output is correct
36 Correct 1979 ms 37360 KB Output is correct
37 Correct 1986 ms 37100 KB Output is correct