Submission #58887

#	Time	Username	Problem	Language	Result	Execution time	Memory
58887		TadijaSebez	Construction of Highway (JOI18_construction)	C++11	100 / 100	500 ms	90284 KiB

construction

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100050;
vector<int> E[N];
int c[N];
struct BIT
{
	int sum[N];
	vector<int> use;
	void init(){ for(int i=0;i<use.size();i++) sum[use[i]]=0;use.clear();}
	BIT(){}
	void Set(int i, int x){ for(;i<N;i+=i&-i){ if(!sum[i]) use.pb(i);sum[i]+=x;}}
	int Get(int i){ int ret=0;for(;i;i-=i&-i) ret+=sum[i];return ret;}
} Tree;
int sz[N],head[N],dep[N],par[N];
vector<pair<int,int> > all[N];
void DFS(int u, int p)
{
	dep[u]=dep[p]+1;
	par[u]=p;
	sz[u]=1;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p) DFS(v,u),sz[u]+=sz[v];
	}
}
void HLD(int u, int p)
{
	if(!p) head[u]=u;
	int HC=0,i;
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p && sz[v]>sz[HC]) HC=v;
	}
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p)
		{
			if(v==HC) head[v]=head[u];
			else head[v]=v;
			HLD(v,u);
		}
	}
}
ll Query(int u, int v)
{
	ll ans=0;
	int col=c[v];
	vector<pair<int,int> > work;
	while(u)
	{
		int len=dep[u]-dep[head[u]]+1;
		int chain=head[u];
		work.clear();
		while(all[chain].size() && len>=all[chain].back().first)
		{
			work.pb(all[chain].back());
			len-=all[chain].back().first;
			all[chain].pop_back();
		}
		if(all[chain].size() && len>0)
		{
			work.pb(mp(len,all[chain].back().second));
			all[chain][all[chain].size()-1].first-=len;
		}
		while(work.size())
		{
			ans+=(ll)work.back().first*Tree.Get(work.back().second-1);
			Tree.Set(work.back().second,work.back().first);
			//printf("del:%i %i\n",work.back().first,work.back().second);
			work.pop_back();
		}
		u=par[head[u]];
	}
	while(v)
	{
		int push=dep[v]-dep[head[v]]+1;
		all[head[v]].pb(mp(push,col));
		//printf("add:%i %i\n",push,col);
		//printf("%i %i %i %i\n",head[v],v,push,col);
		v=par[head[v]];
	}
	Tree.init();
	return ans;
}
vector<int> id;
int Find(int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;}
int a[N],b[N];
int main()
{
	int n,i,u,v;
	scanf("%i",&n);
	for(i=1;i<=n;i++) scanf("%i",&c[i]),id.pb(c[i]);
	sort(id.begin(),id.end());
	id.erase(unique(id.begin(),id.end()),id.end());
	for(i=1;i<=n;i++) c[i]=Find(c[i]);
	for(i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),a[i]=u,b[i]=v;
	DFS(1,0);
	HLD(1,0);
	all[1].pb(mp(1,c[1]));
	for(i=1;i<n;i++) printf("%lld\n",Query(a[i],b[i]));
	return 0;
}

Compilation message (stderr)

construction.cpp: In member function 'void BIT::init()':
construction.cpp:15:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  void init(){ for(int i=0;i<use.size();i++) sum[use[i]]=0;use.clear();}
                           ~^~~~~~~~~~~
construction.cpp: In function 'void DFS(int, int)':
construction.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
construction.cpp: In function 'void HLD(int, int)':
construction.cpp:37:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~
construction.cpp:42:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
construction.cpp:101:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%i",&c[i]),id.pb(c[i]);
                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
construction.cpp:105:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),a[i]=u,b[i]=v;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84