oj.uz

Submission #372220

# Submission time Handle Problem Language Result Execution time Memory
372220 2021-02-27T09:38:16 Z MahdiBahramian Factories (JOI14_factories) C++11
100 / 100
 4000 ms 127308 KB 
#include "factories.h"
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,fast-math")
#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:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 1 ; i < verts.size() ; i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:72: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]
   72 |  for(int i = 0 ; i < srt1.size() - 1 ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12524 KB Output is correct
2 Correct 979 ms 21076 KB Output is correct
3 Correct 951 ms 21232 KB Output is correct
4 Correct 944 ms 21268 KB Output is correct
5 Correct 839 ms 21568 KB Output is correct
6 Correct 765 ms 21164 KB Output is correct
7 Correct 966 ms 20972 KB Output is correct
8 Correct 928 ms 21200 KB Output is correct
9 Correct 873 ms 21508 KB Output is correct
10 Correct 776 ms 21140 KB Output is correct
11 Correct 926 ms 21100 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 1800 ms 96564 KB Output is correct
3 Correct 2564 ms 98936 KB Output is correct
4 Correct 1271 ms 97236 KB Output is correct
5 Correct 2842 ms 127308 KB Output is correct
6 Correct 2766 ms 100420 KB Output is correct
7 Correct 2301 ms 37480 KB Output is correct
8 Correct 1162 ms 38072 KB Output is correct
9 Correct 2339 ms 41640 KB Output is correct
10 Correct 2153 ms 38764 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12524 KB Output is correct
2 Correct 979 ms 21076 KB Output is correct
3 Correct 951 ms 21232 KB Output is correct
4 Correct 944 ms 21268 KB Output is correct
5 Correct 839 ms 21568 KB Output is correct
6 Correct 765 ms 21164 KB Output is correct
7 Correct 966 ms 20972 KB Output is correct
8 Correct 928 ms 21200 KB Output is correct
9 Correct 873 ms 21508 KB Output is correct
10 Correct 776 ms 21140 KB Output is correct
11 Correct 926 ms 21100 KB Output is correct
12 Correct 11 ms 12268 KB Output is correct
13 Correct 1800 ms 96564 KB Output is correct
14 Correct 2564 ms 98936 KB Output is correct
15 Correct 1271 ms 97236 KB Output is correct
16 Correct 2842 ms 127308 KB Output is correct
17 Correct 2766 ms 100420 KB Output is correct
18 Correct 2301 ms 37480 KB Output is correct
19 Correct 1162 ms 38072 KB Output is correct
20 Correct 2339 ms 41640 KB Output is correct
21 Correct 2153 ms 38764 KB Output is correct
22 Correct 2776 ms 102272 KB Output is correct
23 Correct 2826 ms 103160 KB Output is correct
24 Correct 3232 ms 105548 KB Output is correct
25 Correct 3422 ms 106932 KB Output is correct
26 Correct 3709 ms 100844 KB Output is correct
27 Correct 3447 ms 127076 KB Output is correct
28 Correct 2136 ms 104268 KB Output is correct
29 Correct 3839 ms 100408 KB Output is correct
30 Correct 3949 ms 99756 KB Output is correct
31 Correct 4000 ms 100460 KB Output is correct
32 Correct 1709 ms 45704 KB Output is correct
33 Correct 1304 ms 41452 KB Output is correct
34 Correct 1790 ms 35708 KB Output is correct
35 Correct 1598 ms 35784 KB Output is correct
36 Correct 1961 ms 36392 KB Output is correct
37 Correct 1883 ms 36332 KB Output is correct