oj.uz

Submission #364907

# Submission time Handle Problem Language Result Execution time Memory
364907 2021-02-10T12:33:07 Z ogibogi2004 Factories (JOI14_factories) C++14
15 / 100
 3471 ms 255760 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e17;
const int MAXN=5e5+6;
const int lg=20;
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 32 ms 30444 KB Output is correct
2 Correct 589 ms 45164 KB Output is correct
3 Correct 749 ms 45164 KB Output is correct
4 Correct 740 ms 45292 KB Output is correct
5 Correct 739 ms 45548 KB Output is correct
6 Correct 329 ms 45292 KB Output is correct
7 Correct 747 ms 45620 KB Output is correct
8 Correct 787 ms 45584 KB Output is correct
9 Correct 742 ms 45804 KB Output is correct
10 Correct 329 ms 45292 KB Output is correct
11 Correct 736 ms 45516 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 30060 KB Output is correct
2 Incorrect 3471 ms 255760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 30444 KB Output is correct
2 Correct 589 ms 45164 KB Output is correct
3 Correct 749 ms 45164 KB Output is correct
4 Correct 740 ms 45292 KB Output is correct
5 Correct 739 ms 45548 KB Output is correct
6 Correct 329 ms 45292 KB Output is correct
7 Correct 747 ms 45620 KB Output is correct
8 Correct 787 ms 45584 KB Output is correct
9 Correct 742 ms 45804 KB Output is correct
10 Correct 329 ms 45292 KB Output is correct
11 Correct 736 ms 45516 KB Output is correct
12 Correct 23 ms 30060 KB Output is correct
13 Incorrect 3471 ms 255760 KB Output isn't correct
14 Halted 0 ms 0 KB -