Submission #92089

#	Time	Username	Problem	Language	Result	Execution time	Memory
92089		maruii	Construction of Highway (JOI18_construction)	C++17	100 / 100	825 ms	23668 KiB

construction

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
const int SIZE = 1<<17;
#define ff first
#define ss second
int A[MAXN], B[MAXN], C[MAXN], dth[MAXN], prt[17][MAXN], dfn[MAXN], edfn[MAXN], dfnn;
vector<int> edge[100001];
void dfs(int x){
	dfn[x] = ++dfnn;
	for(auto &i: edge[x]){
		prt[0][i] = x;
		dth[i] = dth[x]+1;
		dfs(i);
	}
	edfn[x] = dfnn;
}
struct ST{
	int data[2*SIZE];
	void update(int x, int v){
		for(x+=SIZE; x; x>>=1)
			data[x] = max(data[x], v);
	}
	int query(int s, int e){
		int ret = 0;
		for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
			if(s&1) ret = max(ret, data[s++]);
			if(~e&1) ret = max(ret, data[e--]);
		}
		return ret;
	}
	int lb(int x, int v){
		for(x+=SIZE; data[x]<=v; x=(x-1)/2);
		for(; x<SIZE; x = x<<1|(data[x<<1|1]>v));
		return x-SIZE;
	}
	int rb(int x, int v){
		for(x+=SIZE; data[x]<=v; x=(x+1)/2);
		for(; x<SIZE; x = (x<<1|1)-(data[x<<1]>v));
		return x-SIZE;
	}
} seg;
struct BIT{
	int data[SIZE+1];
	void update(int x, int v){
		for(; x<=SIZE; x+=x&-x) data[x] += v;
	}
	int query(int x){
		int ret=0;
		for(; x; x-=x&-x) ret+= data[x];
		return ret;
	}
} bit;
vector<int> cc;
int main(){
	int N;
	scanf("%d",&N);
	for(int i=1; i<=N; ++i) scanf("%d",C+i), cc.push_back(C[i]);
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	for(int i=1; i<=N; ++i) C[i] = lower_bound(cc.begin(), cc.end(), C[i])-cc.begin()+1;
	for(int i=1; i<N; ++i){
		scanf("%d%d",A+i,B+i);
		edge[A[i]].push_back(B[i]);
	}
	B[0] = 1;
	dth[1] = 1;
	dfs(1);
	for(int i=1; i<17; ++i)for(int j=1; j<=N; ++j) prt[i][j] = prt[i-1][prt[i-1][j]];
	seg.update(0, 1e9); seg.update(N+1, 1e9);
	for(int i=1; i<N; ++i){
		int x = A[i];
		long long ans = 0;
		vector<pair<int, int> > vec;
		while(x){
			int t = seg.query(dfn[x], edfn[x]);
			int l = seg.lb(dfn[x], t), r = seg.rb(edfn[x], t);
			int y = x;
			for(int j=16; j>=0; --j) if(l<dfn[prt[j][x]] && r>edfn[prt[j][x]]) x = prt[j][x];
			x = prt[0][x];
			vec.push_back({C[B[t]], dth[y]-dth[x]});
		}
		for(auto &i: vec){
			ans += 1ll*bit.query(i.ff-1)*i.ss;
			bit.update(i.ff, i.ss);
		}
		printf("%lld\n",ans);
		for(auto &i: vec) bit.update(i.ff, -i.ss);
		seg.update(dfn[B[i]], i);
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
construction.cpp:58:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; ++i) scanf("%d",C+i), cc.push_back(C[i]);
                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",A+i,B+i);
   ~~~~~^~~~~~~~~~~~~~~~

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