Submission #712418

#	Time	Username	Problem	Language	Result	Execution time	Memory
712418		Antekb	Construction of Highway (JOI18_construction)	C++17	100 / 100	588 ms	34172 KiB

construction

#include<bits/stdc++.h>

#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end()

using namespace std;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=1<<17;
vi E[N];
int pre[N], sz[N], par[N], sci[N], dep[N], val[N], co[N];
int wsk;
void dfs_sz(int v){
	for(int u:E[v]){
		if(u!=par[v]){
			par[u]=v;
			dep[u]=dep[v]+1;
			dfs_sz(u);
			sz[v]+=sz[u];
		}
	}
	sz[v]+=1;
	for(int &u:E[v])if(u==par[v])swap(u, E[v].back());
	if(v!=1)E[v].pp();
	for(int &u:E[v])if(sz[u]>sz[E[v][0]])swap(u, E[v][0]);
	//deb(v, E[v].size());
}
void dfs(int v){
	co[wsk]=v;
	pre[v]=wsk++;
	for(int u:E[v]){
		//deb(v, u);
		if(u==E[v][0])sci[wsk]=sci[pre[v]];
		else{
			sci[wsk]=wsk;
			//deb(v, wsk);
		}
		dfs(u);
	}
}
set<int> S[N];
int sum[N+N];
int add(int v, int c){
	int ans=0;
	for(v+=N; v; v>>=1){
		sum[v]+=c;
		if(!(v&1)){
			ans+=sum[v+1];
		}
	}
	return ans;
}
ll calc(int v){
	vector<pair<int, int> > V;
	v=pre[v];
	int t=val[v];
	bool czy=1;
	while(true){
		int u=sci[v];
		//deb(v, u, S[u].size());
		if(S[u].size()){
			//deb(*S[u].begin());
		}
		vector<pair<int, int> > V2;
		int prv=u-1;
		while(prv<v-czy){
			//deb("a");
			//assert(S[u].size());
			int a=*S[u].begin();
			if(a>v-czy){
				V2.eb(v-czy-prv, val[a]);
			}
			else{
				V2.eb(a-prv, val[a]);
				S[u].erase(a);
			}
			prv=a;
		}
		reverse(all(V2));
		for(pii &i:V2)V.pb(i);
		S[u].insert(v);
		val[v]=t;
		if(u==0)break;
		v=pre[par[co[u]]];
		czy=0;
	}
	reverse(all(V));
	//deb(V.size());
	for(pii i:V){
		//deb(i.st, i.nd);
	}
	ll ans=0;
	for(int i=0; i<V.size(); i++){
		ans+=V[i].st*1ll*add(V[i].nd, V[i].st);
	}
	for(int i=0; i<V.size(); i++){
		add(V[i].nd, -V[i].st);
	}
	//assert(sum[1]==0);
	/*ll ans2=0;
	for(int i=0; i<V.size(); i++){
		for(int j=0; j<i; j++){
			if(V[j].nd>V[i].nd)ans2+=V[j].st*1ll*V[i].st;
		}
	}
	assert(ans==ans2);*/
	return ans;
}
int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	map<int, int> M;
	vi V(n);
	for(int &i:V)cin>>i, M[i]=1;
	int wsk2=1;
	for(auto &i:M){
		i.nd=wsk2++;
	}
	vector<pii> edg(n-1);
	for(pii &i:edg)cin>>i.st>>i.nd, E[i.st].pb(i.nd), E[i.nd].pb(i.st);
	dfs_sz(1);
	dfs(1);
	for(int i=1; i<=n; i++){
		//deb(i, pre[i], par[i], val[i], sci[pre[i]], sz[i]);
	}
	S[0].insert(0);
	for(int i=1; i<=n; i++){
		val[pre[i]]=M[V[i-1]];
	}
	for(pii i:edg){
		cout<<calc(i.nd)<<"\n";
	}
}

Compilation message (stderr)

construction.cpp: In function 'll calc(int)':
construction.cpp:108:10: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  108 |  for(pii i:V){
      |          ^
construction.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
construction.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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