oj.uz

Submission #364913

# Submission time Handle Problem Language Result Execution time Memory
364913 2021-02-10T12:38:18 Z ogibogi2004 Factories (JOI14_factories) C++14
100 / 100
 7976 ms 321504 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e17;
const int MAXN=1e6+6;
const int lg=21;
ll ans;
vector<pair<int,ll> >g[MAXN];
vector<int>g1[MAXN];
int par[MAXN];
pair<int,int> dp[2*MAXN][lg];
int depth[MAXN];
ll depth1[MAXN];
int pw[2*MAXN],n;
int wherel[MAXN],wherer[MAXN];
vector<int>dfs_order;
int st[MAXN];
bool f[MAXN];
ll mind[MAXN];
void dfs1(int u,int p)
{
	dfs_order.push_back(u);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		depth1[v.first]=depth1[u]+v.second;
		depth[v.first]=depth[u]+1;
		dfs1(v.first,u);
		dfs_order.push_back(u);
	}
}
void precompute()
{
	int t=1,c=0;
	for(int i=1;i<=MAXN;i++)
	{
		if(t*2<=i)
		{
			t*=2;c++;
		}
		pw[i]=c;
	}
	for(int i=0;i<dfs_order.size();i++)
	{
		dp[i][0]={depth[dfs_order[i]],dfs_order[i]};
	}
	for(int i=0;i<dfs_order.size();i++)
	{
		wherer[dfs_order[i]]=i;
	}
	
	for(int i=dfs_order.size()-1;i>=0;i--)
	{
		wherel[dfs_order[i]]=i;
	}
	for(int step=1;step<lg;step++)
	{
		for(int i=0;i<dfs_order.size();i++)
		{
			dp[i][step]=dp[i][step-1];
			if(i+(1<<(step-1))<dfs_order.size())
			{
				dp[i][step]=min(dp[i][step],dp[i+(1<<(step-1))][step-1]);
			}
		}
	}
}
int lca(int x,int y)
{
	if(wherel[x]>wherel[y])swap(x,y);
	int i1=wherel[x];
	int i2=wherer[y];
	int d=i2-i1+1;
	int t=pw[d];
	pair<int,int>ret=dp[i1][t];
	ret=min(ret,dp[i2-(1<<t)+1][t]);
	return ret.second;
}
ll dist(int x,int y)
{
	return depth1[x]+depth1[y]-2*depth1[lca(x,y)];
}
void dfs2(int u,int p)
{
	st[u]=1;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		dfs2(v.first,u);
		st[u]+=st[v.first];
	}
}
int find(int u,int p,int t)
{
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		if(st[v.first]>t/2)return find(v.first,u,t);
	}
	return u;
}
void decompose(int u,int p)
{
	dfs2(u,p);
	int c=find(u,p,st[u]);
	if(p>0)
	{
		g1[p].push_back(c);
	}
	par[c]=p;
	f[c]=1;
	for(auto v:g[c])
	{
		if(f[v.first])continue;
		decompose(v.first,c);
	}
}
void Init(int N, int A[], int B[], int D[]) {
	n=N;
	for(int i=0;i<n-1;i++)
	{
		g[A[i]+1].push_back({B[i]+1,D[i]});
		g[B[i]+1].push_back({A[i]+1,D[i]});
	}
	dfs1(1,0);
	precompute();
	decompose(1,-1);
	for(int i=0;i<MAXN;i++)mind[i]=INF;
}
void update(int x)
{
	mind[x]=0;
	int y=par[x];
	while(y>0)
	{
		mind[y]=min(mind[y],dist(x,y));
		y=par[y];
	}
}
void clear(int x)
{
	mind[x]=INF;
	int y=par[x];
	while(y>0)
	{
		mind[y]=INF;
		y=par[y];
	}
}
void check(int x)
{
	ans=min(ans,mind[x]);
	int y=par[x];
	while(y>0)
	{
		ans=min(ans,mind[y]+dist(x,y));
		y=par[y];
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	ans=INF;
	for(int i=0;i<S;i++)
	{
		update(X[i]+1);
	}
	for(int i=0;i<T;i++)
	{
		check(Y[i]+1);
	}
	for(int i=0;i<S;i++)
	{
		clear(X[i]+1);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'void precompute()':
factories.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
factories.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
factories.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i=0;i<dfs_order.size();i++)
      |               ~^~~~~~~~~~~~~~~~~
factories.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    if(i+(1<<(step-1))<dfs_order.size())
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 59628 KB Output is correct
2 Correct 609 ms 69352 KB Output is correct
3 Correct 804 ms 69572 KB Output is correct
4 Correct 743 ms 69504 KB Output is correct
5 Correct 766 ms 69740 KB Output is correct
6 Correct 382 ms 69484 KB Output is correct
7 Correct 778 ms 69484 KB Output is correct
8 Correct 751 ms 69736 KB Output is correct
9 Correct 756 ms 69868 KB Output is correct
10 Correct 333 ms 69356 KB Output is correct
11 Correct 740 ms 69612 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 59372 KB Output is correct
2 Correct 3578 ms 287304 KB Output is correct
3 Correct 4777 ms 290340 KB Output is correct
4 Correct 1427 ms 281928 KB Output is correct
5 Correct 5759 ms 321504 KB Output is correct
6 Correct 4839 ms 292016 KB Output is correct
7 Correct 2668 ms 113704 KB Output is correct
8 Correct 692 ms 112860 KB Output is correct
9 Correct 2659 ms 118552 KB Output is correct
10 Correct 2697 ms 114600 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 59628 KB Output is correct
2 Correct 609 ms 69352 KB Output is correct
3 Correct 804 ms 69572 KB Output is correct
4 Correct 743 ms 69504 KB Output is correct
5 Correct 766 ms 69740 KB Output is correct
6 Correct 382 ms 69484 KB Output is correct
7 Correct 778 ms 69484 KB Output is correct
8 Correct 751 ms 69736 KB Output is correct
9 Correct 756 ms 69868 KB Output is correct
10 Correct 333 ms 69356 KB Output is correct
11 Correct 740 ms 69612 KB Output is correct
12 Correct 42 ms 59372 KB Output is correct
13 Correct 3578 ms 287304 KB Output is correct
14 Correct 4777 ms 290340 KB Output is correct
15 Correct 1427 ms 281928 KB Output is correct
16 Correct 5759 ms 321504 KB Output is correct
17 Correct 4839 ms 292016 KB Output is correct
18 Correct 2668 ms 113704 KB Output is correct
19 Correct 692 ms 112860 KB Output is correct
20 Correct 2659 ms 118552 KB Output is correct
21 Correct 2697 ms 114600 KB Output is correct
22 Correct 4844 ms 288888 KB Output is correct
23 Correct 4994 ms 291124 KB Output is correct
24 Correct 6903 ms 291924 KB Output is correct
25 Correct 6886 ms 295608 KB Output is correct
26 Correct 7086 ms 292360 KB Output is correct
27 Correct 7976 ms 318216 KB Output is correct
28 Correct 1740 ms 286376 KB Output is correct
29 Correct 6978 ms 292640 KB Output is correct
30 Correct 6904 ms 291988 KB Output is correct
31 Correct 7041 ms 292712 KB Output is correct
32 Correct 2776 ms 124584 KB Output is correct
33 Correct 706 ms 118364 KB Output is correct
34 Correct 2155 ms 116192 KB Output is correct
35 Correct 2195 ms 116256 KB Output is correct
36 Correct 2700 ms 116960 KB Output is correct
37 Correct 2658 ms 116904 KB Output is correct