Submission #49255

#	Time	Username	Problem	Language	Result	Execution time	Memory
49255		spencercompton	Construction of Highway (JOI18_construction)	C++17	100 / 100	873 ms	7128 KiB

construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int l[100000];
int r[100000];
int p[100000];
int sub[100000];
int pri[100000];
int val[100000];
int par[100000];
void pull(int t){
	sub[t] = 1;
	if(l[t]!=-1){
		sub[t] += sub[l[t]];
		p[l[t]] = t;
	}
	if(r[t]!=-1){
		sub[t] += sub[r[t]];
		p[r[t]] = t;
	}
}
void push(int t){
	if(l[t]!=-1){
		val[l[t]] = val[t];
	}
	if(r[t]!=-1){
		val[r[t]] = val[t];
	}
}
int merge(int le, int ri){
	if(le==-1 && ri==-1){
		return -1;
	}
	if(le==-1){
		return ri;
	}
	if(ri==-1){
		return le;
	}
	push(le);
	push(ri);
	if(pri[le]>pri[ri]){
		r[le] = merge(r[le],ri);
		pull(le);
		return le;
	}
	else{
		l[ri] = merge(le,l[ri]);
		pull(ri);
		return ri;
	}
}
pair<int, int> split(int t, int k){
	if(t==-1){
		return make_pair(-1,-1);
	}
	push(t);
	int lsum = 0;
	if(l[t]!=-1){
		lsum = sub[l[t]];
	}
	if(lsum>=k){
		pair<int, int> ret = split(l[t],k);
		l[t] = ret.second;
		ret.second = t;
		pull(t);
		return ret;
	}
	else{
		pair<int, int> ret = split(r[t],k-lsum-1);
		r[t] = ret.first;
		ret.first = t;
		pull(t);
		return ret;
	}
}
pair<int, int> dfs(int now, int from){
	int ret = 0;
	if(from==-1 && l[now]!=-1){
		ret += sub[l[now]];
	}
	if(from!=-1 && r[now]==from){
		ret++;
		if(l[now]!=-1){
			ret += sub[l[now]];
		}
	}
	if(p[now]==-1){
		return make_pair(now,ret);
	}
	pair<int, int> get = dfs(p[now],now);
	get.second += ret;
	return get;
}
int first(int now){
	if(l[now]==-1){
		return now;
	}
	return first(l[now]);
}
void dfs2(int now){
	cout << "NOW " << now << endl;
	if(l[now]!=-1){
		cout << "LEFT " << now << " -> " << l[now] << endl;
		dfs2(l[now]);
	}
	if(r[now]!=-1){
		cout << "RIGHT " << now << " -> " << r[now] << endl;
		dfs2(r[now]);
	}
}
vector<pair<int, int> > compress(vector<pair<int, int> > a){
	vector<int> all;
	for(int i = 0; i<a.size(); i++){
		all.push_back(a[i].first);
	}
	sort(all.begin(),all.end());
	int p =1;
	map<int, int> m;
	for(int i = 0; i<a.size(); i++){
		if(i==0 || all[i]!=all[i-1]){
			m[all[i]] = p++;
		}
	}
	for(int i = 0; i<a.size(); i++){
		a[i].first = m[a[i].first];
	}
	return a;
}
class Fenwick{
	public:
		vector<ll> li;
		int n;
		Fenwick(int a){
			n = a;
			li.resize(n+5);
		}
		void add(int ind, ll val){
			for(;ind<n; ind+=(ind&(-ind))){
				li[ind] += val;
			}
		}
		ll get(int ind){
			ll ret = 0LL;
			for(;ind>0; ind-=(ind&(-ind))){
				ret += li[ind];
			}
			return ret;
		}
 
};
int main(){
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	srand(11);
	int n;
	scanf("%d",&n);
	for(int i = 0; i<n; i++){
		l[i] = -1;
		r[i] = -1;
		p[i] = -1;
		sub[i] = 1;
		pri[i] = rand();
		scanf("%d",&val[i]);
		par[i] = -1;
	}
	for(int i = 0; i+1<n; i++){
		int a, b;
		scanf("%d %d",&a,&b);
		a--;
		b--;
		vector<pair<int, int> > li;
		//not including now
		int now = a;
		int set = val[b];
		pair<int, int> got = dfs(now,-1);
		int ind = got.second;
		int root = got.first;
		pair<int, int> both = split(root,ind+1);
		if(both.first!=-1){
			p[both.first] = -1;
		}
		if(both.second!=-1){
			p[both.second] = -1;
		}
		got = dfs(now,-1);
		ind = got.second;
		root = got.first;
		li.push_back(make_pair(val[got.first],1));
		while(true){
			got = dfs(now,-1);
			ind = got.second;
			root = got.first;
			int f = first(root);
			int all = val[root];
			if(par[f]==-1){
				//started from the bottom, now we here
				li.push_back(make_pair(all,ind));
				val[root] = set;
				now = f;
				break;
			}
			else{
				li.push_back(make_pair(all,ind));
				int nex = par[f];
				pair<int, int> got2 = dfs(nex,-1);
				int ind2 = got2.second;
				int root2 = got2.first;
				pair<int, int> both2 = split(root2,ind2+1);
				if(both2.first!=-1){
					p[both2.first] = -1;
				}
				if(both2.second!=-1){
					p[both2.second] = -1;
				}
				now = f;
				int nval = val[both2.first];
				val[merge(both2.first,root)] = nval;
			}
		}
		got = dfs(now,-1);
		root = got.first;
		par[b] = a;
		val[merge(root,b)] = set;
		li =compress(li);
		Fenwick fen = Fenwick(li.size());
		ll all = 0LL;
		ll ans = 0LL;
		for(int i = li.size()-1; i>=0; i--){
			ans += (all-fen.get(li[i].first))*(ll)li[i].second;
			fen.add(li[i].first,li[i].second);
			all += li[i].second;
		}
      	printf("%lld\n",ans);
	}
}

Compilation message (stderr)

construction.cpp: In function 'std::vector<std::pair<int, int> > compress(std::vector<std::pair<int, int> >)':
construction.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<a.size(); i++){
                 ~^~~~~~~~~
construction.cpp:120:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<a.size(); i++){
                 ~^~~~~~~~~
construction.cpp:125:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<a.size(); i++){
                 ~^~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
construction.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&val[i]);
   ~~~~~^~~~~~~~~~~~~~
construction.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~

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