oj.uz

Submission #364910

# Submission time Handle Problem Language Result Execution time Memory
364910 2021-02-10T12:34:10 Z ogibogi2004 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 401484 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e17;
const int MAXN=2e6+6;
const int lg=23;
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 88 ms 118380 KB Output is correct
2 Correct 653 ms 128336 KB Output is correct
3 Correct 800 ms 128236 KB Output is correct
4 Correct 781 ms 128400 KB Output is correct
5 Correct 781 ms 128620 KB Output is correct
6 Correct 372 ms 128284 KB Output is correct
7 Correct 780 ms 128364 KB Output is correct
8 Correct 787 ms 128364 KB Output is correct
9 Correct 796 ms 128748 KB Output is correct
10 Correct 370 ms 128108 KB Output is correct
11 Correct 778 ms 128236 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 118252 KB Output is correct
2 Correct 3570 ms 361764 KB Output is correct
3 Correct 4720 ms 373652 KB Output is correct
4 Correct 1458 ms 361980 KB Output is correct
5 Correct 5808 ms 401484 KB Output is correct
6 Correct 4936 ms 371636 KB Output is correct
7 Correct 2745 ms 183240 KB Output is correct
8 Correct 763 ms 181188 KB Output is correct
9 Correct 2757 ms 186764 KB Output is correct
10 Correct 2794 ms 182608 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 118380 KB Output is correct
2 Correct 653 ms 128336 KB Output is correct
3 Correct 800 ms 128236 KB Output is correct
4 Correct 781 ms 128400 KB Output is correct
5 Correct 781 ms 128620 KB Output is correct
6 Correct 372 ms 128284 KB Output is correct
7 Correct 780 ms 128364 KB Output is correct
8 Correct 787 ms 128364 KB Output is correct
9 Correct 796 ms 128748 KB Output is correct
10 Correct 370 ms 128108 KB Output is correct
11 Correct 778 ms 128236 KB Output is correct
12 Correct 79 ms 118252 KB Output is correct
13 Correct 3570 ms 361764 KB Output is correct
14 Correct 4720 ms 373652 KB Output is correct
15 Correct 1458 ms 361980 KB Output is correct
16 Correct 5808 ms 401484 KB Output is correct
17 Correct 4936 ms 371636 KB Output is correct
18 Correct 2745 ms 183240 KB Output is correct
19 Correct 763 ms 181188 KB Output is correct
20 Correct 2757 ms 186764 KB Output is correct
21 Correct 2794 ms 182608 KB Output is correct
22 Correct 4833 ms 363768 KB Output is correct
23 Correct 4994 ms 366060 KB Output is correct
24 Correct 7082 ms 367064 KB Output is correct
25 Correct 7118 ms 370696 KB Output is correct
26 Correct 7183 ms 367204 KB Output is correct
27 Execution timed out 8053 ms 392940 KB Time limit exceeded
28 Halted 0 ms 0 KB -