Submission #100750

#	Time	Username	Problem	Language	Result	Execution time	Memory
100750		TAISA_	Construction of Highway (JOI18_construction)	C++14	16 / 100	2035 ms	8056 KiB

construction

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
template<typename T> void chmax(T &a,T b){a=max(a,b);}
template<typename T> void chmin(T &a,T b){a=min(a,b);}
vector<vector<int>> G;
struct BIT{
	vector<int> bit;
	BIT(int n){
		bit.resize(n+1,0);
	}
	void add(int k,int x){
		for(++k;k<bit.size();k+=k&-k){
			bit[k]+=x;
		}
	}
	int sum(int k){
		int res=0;
		for(++k;k>0;k-=k&-k){
			res+=bit[k];
		}
		return res;
	}
};
int main(){
	int n;cin>>n;
	vector<ll> c(n);
	G.resize(n);
	vector<int> par(n,-1);
	for(int i=0;i<n;i++)cin>>c[i];
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;--a;--b;
		G[a].push_back(b);
		par[b]=a;
		vector<int> v,vv;
		while(a!=-1){
			v.push_back(c[a]);
			vv.push_back(c[a]);
			c[a]=c[b];
			a=par[a];
		}
		sort(all(vv));
		map<int,int> mp;
		for(int j=0;j<vv.size();j++){
			mp[vv[j]]=j;
		}
		reverse(all(v));
		int ans=0;
		BIT bit(vv.size());
		for(int j=0;j<v.size();j++){
			v[j]=mp[v[j]];
			ans+=bit.sum(vv.size()-1)-bit.sum(v[j]);
			bit.add(v[j],1);
		}
		cout<<ans<<endl;
	}
}

Compilation message (stderr)

construction.cpp: In member function 'void BIT::add(int, int)':
construction.cpp:14:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(++k;k<bit.size();k+=k&-k){
           ~^~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<vv.size();j++){
               ~^~~~~~~~~~
construction.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v.size();j++){
               ~^~~~~~~~~

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