Submission #112236

#	Time	Username	Problem	Language	Result	Execution time	Memory
112236		nxteru	Construction of Highway (JOI18_construction)	C++14	100 / 100	507 ms	89296 KiB

construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct BIT{
	int n;
	ll bit[100005];
	void ini(int x){
		n=x;
		for(int i=0;i<=n;i++)bit[i]=0;
	}
	void add(int a,ll x){
		a++;
		while(a<=n){
			bit[a]+=x;
			a+=(a&-a);
		}
	}
	ll sum(int a){
		a++;
		ll res=0;
		while(a>0){
			res+=bit[a];
			a-=(a&-a);
		}
		return res;
	}
};
int n,k,id[100005],a[100005],b[100005],sz[100005],hd[100005],cn[100005];
vector<int>g[100005],cm;
stack<P>s[100005];
ll q[100005];
BIT bit;
void dfs1(int v){
	sz[v]=1;
	for(int i=0;i<g[v].size();i++){
		dfs1(g[v][i]);
		sz[v]+=sz[g[v][i]];
		if(sz[g[v][0]]<sz[g[v][i]])swap(g[v][0],g[v][i]);
	}
}
void dfs2(int v,int h){
	id[v]=k;
	hd[k]=h;
	cn[k]=cn[h];
	k++;
	if(g[v].size()!=0)dfs2(g[v][0],h);
	s[h].push(P(q[v],1LL));
	for(int i=1;i<g[v].size();i++){
		cn[k]=id[v];
		dfs2(g[v][i],k);
	}
}
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
		scanf("%lld",q+i);
		cm.PB(q[i]);
	}
	sort(cm.begin(),cm.end());
	cm.erase(unique(cm.begin(),cm.end()),cm.end());
	bit.ini(cm.size());
	for(int i=0;i<n;i++)q[i]=lower_bound(cm.begin(),cm.end(),q[i])-cm.begin();
    for(int i=0;i<n-1;i++){
		scanf("%d%d",a+i,b+i);
		a[i]--,b[i]--;
		g[a[i]].PB(b[i]);
	}
	dfs1(0);
	dfs2(0,0);
	for(int i=0;i<n-1;i++){
		vector<P>r;
		stack<P>w;
		ll ans=0;
		int v=a[i],u=b[i];
		v=id[v];
		while(1){
			int h=hd[v],res=v-h+1;
			while(s[h].top().S<=res){
				w.push(s[h].top());
				res-=s[h].top().S;
				s[h].pop();
			}
			if(res>0){
				s[h].top().S-=res;
				w.push(P(s[h].top().F,res));
			}
			s[h].push(P(q[u],ll(v-h+1)));
			while(!w.empty()){
				r.PB(w.top());
				w.pop();
			}
			if(h==0)break;
			else v=cn[h];
		}
		for(int j=0;j<r.size();j++){
			ans+=r[j].S*bit.sum(r[j].F-1);
			bit.add(r[j].F,r[j].S);
		}
		for(int j=0;j<r.size();j++)bit.add(r[j].F,-r[j].S);
		printf("%lld\n",ans);
	}
}

Compilation message (stderr)

construction.cpp: In function 'void dfs1(int)':
construction.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
construction.cpp: In function 'void dfs2(int, int)':
construction.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<g[v].size();i++){
              ~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<r.size();j++){
               ~^~~~~~~~~
construction.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<r.size();j++)bit.add(r[j].F,-r[j].S);
               ~^~~~~~~~~
construction.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
construction.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",q+i);
   ~~~~~^~~~~~~~~~~~
construction.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",a+i,b+i);
   ~~~~~^~~~~~~~~~~~~~~~

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