Submission #57071

#	Time	Username	Problem	Language	Result	Execution time	Memory
57071		cki86201	Construction of Highway (JOI18_construction)	C++11	100 / 100	1152 ms	24284 KiB

construction

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
typedef tuple<int, int, int> t3;

int N, C[100010];
int In[100010][2];
vector <int> E[100010];
int st[100010], en[100010], ce;
int up[100010][20], dep[100010];

void dfs(int x, int fa) {
	st[x] = ++ce;
	for(int e : E[x]) if(e != fa) {
		dep[e] = dep[x] + 1;
		up[e][0] = x;
		for(int i=1;i<20;i++) up[e][i] = up[ up[e][i-1] ][i-1];
		dfs(e, x);
	}
	en[x] = ce;
}

const int TADD = 1<<17;
int T[1<<18];
int get_max(int l, int r) {
	l += TADD, r += TADD;
	int res = 0;
	while(l <= r) {
		if(l&1) res = max(res, T[l++]);
		if(!(r&1)) res = max(res, T[r--]);
		l >>= 1, r >>= 1;
	}
	return res;
}
int get_node(int x) { return get_max(st[x], en[x]); }
void upd(int x, int v) {
	x += TADD;
	while(x) T[x] = v, x >>= 1;
}
int stamp;
int max_bit[100010];

int bt[100010];
void updb(int x, int v) {
	for(int i=x;i<100010;i+=(i&-i)) bt[i] += v;
}
int readb(int x) {
	int res = 0;
	for(int i=x;i;i-=(i&-i)) res += bt[i];
	return res;
}
ll Do(vector <t3> &X) {
	sort(all(X), [](t3 a, t3 b) {
		if(get<1>(a) != get<1>(b)) return get<1>(a) < get<1>(b);
		return get<2>(a) > get<2>(b);
	});
	ll res = 0;
	for(t3 &e : X) {
		res += (ll) get<0>(e) * readb(get<2>(e));
		updb(get<2>(e), get<0>(e));
	}
	for(t3 &e : X) {
		updb(get<2>(e), -get<0>(e));
	}
	return res;
}

int cc[100010];

void solve(){
	for(int i=1;i<100010;i++) max_bit[i] = 31 - __builtin_clz(i);
	scanf("%d", &N);
	vector <int> vc;
	for(int i=1;i<=N;i++) scanf("%d", C + i), vc.pb(C[i]);
	sort(all(vc)); vc.resize(unique(all(vc)) - vc.begin());
	for(int i=1;i<=N;i++) C[i] = (int)(lower_bound(all(vc), C[i]) - vc.begin() + 1);
	for(int i=1;i<N;i++) {
		int x, y; scanf("%d%d", &x, &y);
		In[i][0] = x, In[i][1] = y;
		E[x].pb(y);
	}
	dfs(1, -1);
	upd(st[1], ++stamp); cc[stamp] = C[1];
	for(int i=1;i<N;i++) {
		int b = In[i][1], a = In[i][0];
		vector <t3> R;
		while(a) {
			int val = get_node(a);
			int cnt = 1;
			for(int j=max_bit[dep[a]];j>=0;j--) {
				int val2 = get_node(up[a][j]);
				if(val == val2) {
					cnt += 1<<j;
					a = up[a][j];
				}
			}
			int nr = szz(R);
			R.pb(t3(cnt, cc[val], 1 + nr));
			a = up[a][0];
		}
		printf("%lld\n", Do(R));
		
		upd(st[b], ++stamp);
		cc[stamp] = C[b];
	}
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void solve()':
construction.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
construction.cpp:95:42: 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), vc.pb(C[i]);
                                          ^
construction.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

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