Submission #110639

#	Time	Username	Problem	Language	Result	Execution time	Memory
110639		Pajaraja	Construction of Highway (JOI18_construction)	C++17	0 / 100	8 ms	5376 KiB

construction

#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 18
using namespace std;
vector<int> g[MAXN],vl,br,vr;
int in[MAXN],out[MAXN],p[MAXL][MAXN],t,n,c[MAXN],rd[MAXN],d[MAXN],seg[4*MAXN];
long long bit[MAXN];
map<int,int> mp;
void updseg(int l,int r,int x,int v,int ind)
{
	if(l==r) {seg[ind]=v; return;}
	int s=(l+r)/2;
	if(x<=s) updseg(l,s,x,v,2*ind);
	else updseg(s+1,r,x,v,2*ind+1);
	seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}
int val(int l,int r,int lt,int rt,int ind)
{
	if(l>=lt && r<=rt) return seg[ind];
	if(r<lt || l>rt) return 0;
	int s=(l+r)/2;
	return max(val(l,s,lt,rt,2*ind),val(s+1,r,lt,rt,2*ind+1));
}
void dfs(int s,int dub)
{
	in[s]=++t;
	d[s]=dub;
	for(int i=0;i<g[s].size();i++) dfs(g[s][i],dub+1);
	out[s]=t;
}
void lcainit()
{
	dfs(1,0); p[0][1]=1;
	for(int i=1;i<MAXL;i++) for(int j=1;j<=n;j++) p[i][j]=p[i-1][p[i-1][j]];
}
bool insub(int u,int v) {return in[u]<=in[v] && out[u]>=out[v];}
int lca(int u,int v)
{
	for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][u],v)) u=p[i][u];
	return u;
}
void upd(int x,int val)
{
	while(x<=MAXN)
	{
		bit[x]+=val;
		x+=x&-x;
	}
}
long long fnd(int x)
{
	long long sm=0;
	while(x)
	{
		sm+=bit[x];
		x-=x&-x;
	}
	return sm;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {scanf("%d",&c[i]); vl.push_back(c[i]);}
	sort(vl.begin(),vl.end());
	for(int i=0;i<n;i++) mp[vl[i]]=n-i;
	for(int i=0;i<n;i++) c[i]=mp[c[i]];
	for(int i=0;i<n-1;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		g[t1].push_back(t2);
		p[0][t2]=t1;
		rd[i]=t2;
	}
	lcainit();
	for(int i=0;i<n-1;i++)
	{
		int x=1; long long sol=0;
		while(x!=rd[i])
		{
			int r=val(1,n,in[x],out[x],1);
			int w=lca(rd[i],rd[r]);
			br.push_back(c[rd[r]]); vr.push_back(d[w]-d[x]);
			sol+=((long long)d[w]-d[x])*fnd(c[rd[r]]-1);
			upd(c[rd[r]],d[w]-d[x]);
			x=w;
		}
		updseg(1,n,in[rd[i]],i,1);
		//for(int i=0;i<br.size();i++) upd(br[i],-vr[i]);
		br.clear(); vr.clear();
		printf("%lld\n",sol);
	}
}

Compilation message (stderr)

construction.cpp: In function 'void dfs(int, int)':
construction.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dfs(g[s][i],dub+1);
              ~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
construction.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) {scanf("%d",&c[i]); vl.push_back(c[i]);}
                         ~~~~~^~~~~~~~~~~~
construction.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
   ~~~~~^~~~~~~~~~~~~~~~

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