Submission #442112

#	Time	Username	Problem	Language	Result	Execution time	Memory
442112		PixelCat	Construction of Highway (JOI18_construction)	C++14	100 / 100	361 ms	26984 KiB

construction

/* code by the cute PixelCat owo */
/*   as cute as nyaaacho neko!   */
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int ll //__int128
#define double long double
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define For(i,a,b)    for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1e17)
#define EPS (1e-6)

#ifdef NYAOWO
#define debug(...) do{\
	cerr << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
	cerr << flush;\
}while(0)
template<typename T> void _OUT(T _X) { cerr << _X << "\n"; }
template<typename T,typename...I>
void _OUT(T _X,I ...tail) { cerr << _X << ", "; _OUT(tail...); }
inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }
#else
#define debug(...)
inline void USACO(const string &s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
#endif
inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*b%mod;
		p/=2; b=b*b%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }

struct BIT{
	int n;
	int a[100010];
	void init(int _n){
		n=_n;
		memset(a,0,sizeof(a));
	}
	void add(int i,int x){
		while(i<=n){
			a[i]+=x;
			i+=LO(i);
		}
	}
	int ask(int i){
		int ans=0;
		while(i>0){
			ans+=a[i];
			i-=LO(i);
		}
		return ans;
	}
}bit;

struct Node{
	vector<int> adj;
	int c;

	int par;
	int nxt;
	int size;
	int dep;

	int head;
	int chainid;
}g[100010];

struct Chain{
	int head,tail;
	int val;
}; vector<Chain> ch[100010];

int dfs(int u,int d){
	g[u].size=1;
	g[u].dep=d;
	int mx=0,id=-1;
	for(auto &i:g[u].adj){
		g[u].size+=dfs(i,d+1);
		if(g[i].size>mx){
			mx=g[i].size; id=i;
		}
	}
	g[u].nxt=id;
	return g[u].size;
}
void build(int u,int h){
	static int chid=0;
	g[u].head=h;
	g[u].chainid=chid;
	if(g[u].nxt!=-1)
		build(g[u].nxt,h);
	for(auto &i:g[u].adj) if(i!=g[u].nxt){
		chid++;
		build(i,i);
	}
}

int link(int u,int v){
	//cerr<<"Query "<<u<<" "<<v<<"\n";

	vector<pii> chid; //chain id,depth
	while(u!=0){
		chid.eb(g[u].chainid,g[u].dep);
		u=g[g[u].head].par;	
	}
	vector<pii> a; //value,count
	Forr(_i,sz(chid)-1,0){
		int &id=chid[_i].F;
		int &d=chid[_i].S;
		Forr(_j,sz(ch[id])-1,0){
			auto &c=ch[id][_j];
			a.eb(c.val,min(c.tail,d)-c.head+1);
			if(c.tail>=d) break;
		}
	}

	int c=g[v].c;
	while(v!=0){
		int id=g[v].chainid;
		int h;
		if(sz(ch[id]))
			h=ch[id].back().head;
		else
			h=g[v].dep;
		while(sz(ch[id]) && ch[id].back().tail<=g[v].dep)
			ch[id].pop_back();
		if(sz(ch[id]) && ch[id].back().head<=g[v].dep)
			ch[id].back().head=g[v].dep+1;
		ch[id].push_back({h,g[v].dep,c});
		v=g[g[v].head].par;
	}

	int ans=0;
	int tot=0;
	for(auto &i:a){
		ans+=i.S*(tot-bit.ask(i.F));
		bit.add(i.F,i.S);
		tot+=i.S;
	}
	for(auto &i:a){
		bit.add(i.F,-i.S);
	}

	/*
	for(auto &i:a)
		cerr<<i.F<<"x"<<i.S<<" ";
	cerr<<"\n";
	For(i,0,1){
		cerr<<"chain "<<i<<" >> ";
		for(auto &j:ch[i])
			cerr<<j.head<<":"<<j.tail<<"="<<j.val<<"  ";
		cerr<<"\n";
	}
	cerr<<"\n";
	*/
	return ans;
}

int32_t main(){
	NYA();
	//nyaacho >/////<
	int n; cin>>n;

	vector<int> al;
	For(i,1,n){
		cin>>g[i].c;
		al.eb(g[i].c);
	}
	sort(all(al));
	al.erase(unique(all(al)),al.end());
	For(i,1,n){
		g[i].c=lower_bound(all(al),g[i].c)-al.begin()+1;
	}
	
	g[1].par=0;
	vector<pii> ed;
	For(i,1,n-1){
		int a,b; cin>>a>>b;
		g[a].adj.eb(b);
		g[b].par=a;
		ed.eb(a,b);
	}

	dfs(1,1);
	build(1,1);

	bit.init(n);
	ch[g[1].chainid].push_back({g[1].dep,g[1].dep,g[1].c});
	for(auto &i:ed){
		cout<<link(i.F,i.S)<<"\n";
	}
	return 0;
}

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