Submission #411793

#	Time	Username	Problem	Language	Result	Execution time	Memory
411793		jamezzz	Construction of Highway (JOI18_construction)	C++14	0 / 100	44 ms	68816 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

#define maxn 100005

int n,c[maxn],a[maxn],b[maxn];
int heavy[maxn],head[maxn],par[maxn],pos[maxn],cur=1;
int ft[maxn];
vi AL[maxn];
vii disc;


struct thing{ int pos,len,val; };

deque<thing> dq[maxn];


int dfs(int u){
	int mx=0,tsz=1;
	for(int v:AL[u]){
		if(v==par[u])continue;
		par[v]=u;
		int sz=dfs(v);
		tsz+=sz;
		if(sz>mx){
			mx=sz;heavy[u]=v;
		}
	}
	return tsz;
}

void decompose(int u,int h){
	head[u]=h;
	pos[u]=cur++;
	if(heavy[u]!=0)decompose(heavy[u],h);
	for(int v:AL[u]){
		if(v==par[u])continue;
		if(v==heavy[u])continue;
		decompose(v,v);
	}
}

void up(int x,int nv){
	while(x<=n)ft[x]+=nv,x+=x&-x;
}

int qry(int x){
	int res=0;
	while(x)res+=ft[x],x-=x&-x;
	return res;
}

ll path(int x){
	memset(ft,0,sizeof ft);
	ll res=0;
	while(x){
		int last=0,hd=head[x];
		for(int i=0;i<sz(dq[hd]);++i){
			thing t=dq[hd][i];
			if(t.pos+t.len-1>=pos[x]){
				last=i;break;
			}
		}
		for(int i=last;i>=0;--i){
			thing t=dq[hd][i];
			int ss=t.pos,ee=min(t.pos+t.len-1,pos[x]);
			int len=ee-ss+1;
			res+=qry(t.val)*len;
			up(t.val+1,len);
		}
		x=par[hd];
	}
	return res;
}

void add_edge(int x,int y){
	debug("add: %d\n",y);
	dq[head[y]].clear();
	dq[head[y]].push_back({pos[head[y]],pos[y]-pos[head[y]]+1,c[y]});
	int cur=par[head[y]];
	while(cur){
		debug("cur: %d\n",cur);
		int last=0,hd=head[cur];
		for(int i=0;i<sz(dq[hd]);++i){
			thing t=dq[hd][i];
			if(t.pos+t.len-1>=pos[cur]){
				last=i;break;
			}
		}
		for(int i=0;i<last;++i)dq[hd].pop_front();
		thing t=dq[hd].front();
		debug("thing: %d %d %d\n",t.pos,t.len,t.val);	
		dq[hd].pop_front();
		int ss=pos[cur]+1,ee=t.pos+t.len-1;
		if(ss>ee)break;
		dq[hd].push_front({ss,ee-ss+1,t.val});
		dq[hd].push_front({pos[hd],pos[cur]-pos[hd]+1,c[y]});
		cur=par[hd];
	}
}

int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		sf("%d",&c[i]);
		disc.pb(c[i],i);
	}
	sort(all(disc));
	int cnt=0,pv=-1;
	for(int i=0;i<n;++i){
		if(disc[i].fi!=pv)++cnt;
		pv=disc[i].fi;
		c[disc[i].se]=cnt;
	}
	for(int i=0;i<n-1;++i){
		sf("%d%d",&a[i],&b[i]);
		AL[a[i]].pb(b[i]);
		AL[b[i]].pb(a[i]);
	}
	
	dfs(1);decompose(1,1);
	dq[1].push_back({1,1,c[1]});

	for(int i=0;i<n-1;++i){
		pf("%lld\n",path(a[i]));
		add_edge(a[i],b[i]);
		#ifdef DEBUG
		for(int j=1;j<=n;++j){
			if(dq[j].empty())continue;
			pf("%d:\n",j);
			for(thing t:dq[j]){
				pf("%d %d %d\n",t.pos,t.len,t.val);
			}
		}
		#endif //DEBUG
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:140:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |  sf("%d",&n);
      |    ^
construction.cpp:142:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   sf("%d",&c[i]);
      |     ^
construction.cpp:153:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |   sf("%d%d",&a[i],&b[i]);
      |     ^

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