oj.uz

Submission #372216

# Submission time Handle Problem Language Result Execution time Memory
372216 2021-02-27T09:30:23 Z MahdiBahramian Factories (JOI14_factories) C++11
100 / 100
 4035 ms 121756 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 37 ms 12524 KB Output is correct
2 Correct 984 ms 21332 KB Output is correct
3 Correct 993 ms 20972 KB Output is correct
4 Correct 1029 ms 21440 KB Output is correct
5 Correct 844 ms 21472 KB Output is correct
6 Correct 848 ms 21180 KB Output is correct
7 Correct 969 ms 21192 KB Output is correct
8 Correct 972 ms 21316 KB Output is correct
9 Correct 932 ms 21460 KB Output is correct
10 Correct 845 ms 21396 KB Output is correct
11 Correct 998 ms 20960 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12268 KB Output is correct
2 Correct 1846 ms 96444 KB Output is correct
3 Correct 2623 ms 97984 KB Output is correct
4 Correct 1344 ms 97308 KB Output is correct
5 Correct 3067 ms 120684 KB Output is correct
6 Correct 2928 ms 99584 KB Output is correct
7 Correct 2249 ms 37396 KB Output is correct
8 Correct 1293 ms 38144 KB Output is correct
9 Correct 2372 ms 40948 KB Output is correct
10 Correct 2230 ms 38940 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12524 KB Output is correct
2 Correct 984 ms 21332 KB Output is correct
3 Correct 993 ms 20972 KB Output is correct
4 Correct 1029 ms 21440 KB Output is correct
5 Correct 844 ms 21472 KB Output is correct
6 Correct 848 ms 21180 KB Output is correct
7 Correct 969 ms 21192 KB Output is correct
8 Correct 972 ms 21316 KB Output is correct
9 Correct 932 ms 21460 KB Output is correct
10 Correct 845 ms 21396 KB Output is correct
11 Correct 998 ms 20960 KB Output is correct
12 Correct 11 ms 12268 KB Output is correct
13 Correct 1846 ms 96444 KB Output is correct
14 Correct 2623 ms 97984 KB Output is correct
15 Correct 1344 ms 97308 KB Output is correct
16 Correct 3067 ms 120684 KB Output is correct
17 Correct 2928 ms 99584 KB Output is correct
18 Correct 2249 ms 37396 KB Output is correct
19 Correct 1293 ms 38144 KB Output is correct
20 Correct 2372 ms 40948 KB Output is correct
21 Correct 2230 ms 38940 KB Output is correct
22 Correct 2958 ms 102372 KB Output is correct
23 Correct 2853 ms 103060 KB Output is correct
24 Correct 3184 ms 104880 KB Output is correct
25 Correct 3345 ms 106164 KB Output is correct
26 Correct 3852 ms 100072 KB Output is correct
27 Correct 3359 ms 121756 KB Output is correct
28 Correct 2155 ms 104112 KB Output is correct
29 Correct 3937 ms 99820 KB Output is correct
30 Correct 4035 ms 99204 KB Output is correct
31 Correct 3977 ms 100052 KB Output is correct
32 Correct 1779 ms 44796 KB Output is correct
33 Correct 1337 ms 41352 KB Output is correct
34 Correct 1805 ms 35844 KB Output is correct
35 Correct 1744 ms 35768 KB Output is correct
36 Correct 2084 ms 36128 KB Output is correct
37 Correct 2145 ms 36032 KB Output is correct