Submission #100441

#	Time	Username	Problem	Language	Result	Execution time	Memory
100441		JPN20	Construction of Highway (JOI18_construction)	C++17	16 / 100	2103 ms	20112 KiB

construction

#include <bits/stdc++.h>
using namespace std;

int size_ = 1, rems = 1;
int va[1 << 18], vb[1 << 18], dat[1 << 18];

void inits(int sz) {
	while (size_ <= sz) size_ *= 2;
	
	int cnt = 1;
	for (int i = size_; i >= 1; i /= 2) {
		for (int j = 0; j < size_; j += i) {
			va[cnt] = j;
			vb[cnt] = j + i;
			cnt++;
		}
	}
}
void update(int pos, int x) {
	pos += size_;
	dat[pos] = x;
	
	while (pos >= 2) {
		pos >>= 1;
		dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
	}
}

int query(int l, int r) {
	// 非再帰 RMQ
	int ret = -(1 << 30);
	int vu[4], vp; vu[0] = 1; vp = 1;
	int cu[4], cp;
	
	while (vp >= 1) {
		cp = 0;
		for (int i = 0; i < vp; i++) {
			int vv = vu[i];
			int vl = va[vv], vr = vb[vv], vm = ((vl + vr) >> 1);
			
			// 左側
			if (l <= vl && vm <= r) ret = max(ret, dat[vv << 1]);
			else if (!(vm <= l || r <= vl)) { cu[cp] = vv * 2; cp++; }
			
			// 右側
			if (l <= vm && vr <= r) ret = max(ret, dat[(vv << 1) + 1]);
			else if (!(vr <= l || r <= vm)) { cu[cp] = vv * 2 + 1; cp++; }
		}
		for (int i = 0; i < cp; i++) vu[i] = cu[i];
		vp = cp;
	}
	return ret;
}

class BIT {
	public:
	vector<int>bit; int size1_;
	
	void init(int sz) {
		size1_ = sz + 2;
		bit.resize(size1_ + 1, 0);
	}
	void add(int pos, int x) {
		pos++;
		while (pos <= size1_) {
			bit[pos] += x; pos += (pos & -pos);
		}
	}
	int sum(int pos) {
		int s = 0; pos++;
		while (pos >= 1) {
			s += bit[pos]; pos -= (pos & -pos);
		}
		return s;
	}
};

long long check_inversions(vector<pair<int, int>> vec) {
	vector<int> A;
	for (int i = 0; i < (int)vec.size(); i++) A.push_back(vec[i].first);
	
	sort(A.begin(), A.end());
	A.erase(unique(A.begin(), A.end()), A.end());
	for (int i = 0; i < (int)vec.size(); i++) vec[i].first = lower_bound(A.begin(), A.end(), vec[i].first) - A.begin();
	
	BIT Z; Z.init(A.size() + 1);
	
	long long ans = 0;
	for (int i = 0; i < (int)vec.size(); i++) {
		ans += 1LL * vec[i].second * (Z.sum(A.size()) - Z.sum(vec[i].first));
		Z.add(vec[i].first, vec[i].second);
	}
	return ans;
}

int N, C[1 << 17], A[1 << 17], B[1 << 17], dist[1 << 17], dp[1 << 17][20];
int cl[1 << 17], cr[1 << 17], cnts;
vector<int> X[1 << 17];

void dfs(int pos, int dep) {
	cnts++; cl[pos] = cnts; dist[pos] = dep;
	for (int i = 0; i < (int)X[pos].size(); i++) {
		if (dist[X[pos][i]] != -1) continue;
		dp[X[pos][i]][0] = pos;
		dfs(X[pos][i], dep + 1);
	}
	cr[pos] = cnts;
}

int prevs(int pos, int x) {
	for (int i = 19; i >= 0; i--) {
		if (x >= (1 << i)) { x -= (1 << i); pos = dp[pos][i]; }
	}
	if (pos == 0) pos = 1;
	return pos;
}

vector<pair<int, int>> get_inverse(int pos) {
	vector<pair<int, int>> U;
	while (true) {
		// Binary Search.
		int L = 0, R = dist[pos] + 1, M, maxn = (1 << 30);
		int E = query(cl[pos], cr[pos] + 1);
		
		for (int i = 0; i < 30; i++) {
			M = (L + R) / 2;
			int G = prevs(pos, M);
			int P = query(cl[G], cr[G] + 1);
			if (E != P) { maxn = min(maxn, M); R = M; }
			else { L = M; }
		}
		
		if (maxn == (1 << 30)) { U.push_back(make_pair(C[B[E]], dist[pos] + 1)); break; }
		U.push_back(make_pair(C[B[E]], maxn));
		pos = prevs(pos, maxn);
		
		rems++;
		assert(rems <= 500000);
	}
	reverse(U.begin(), U.end());
	return U;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &C[i]);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%d%d", &A[i], &B[i]);
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	
	for (int i = 1; i <= N; i++) dist[i] = -1;
	dfs(1, 0);
	
	for (int i = 0; i < 19; i++) {
		for (int j = 1; j <= N; j++) dp[j][i + 1] = dp[dp[j][i]][i];
	}
	
	//for (int i = 1; i <= N; i++) cout << i << ": cl = " << cl[i] << ", cr = " << cr[i] << endl;
	
	inits(N + 2); update(cl[1], 0);
	for (int i = 1; i <= N - 1; i++) {
		vector<pair<int, int>> T = get_inverse(A[i]);
		
		printf("%lld\n", check_inversions(T));
		update(cl[B[i]], i);
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
construction.cpp:146:36: 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]);
                               ~~~~~^~~~~~~~~~~~~
construction.cpp:148: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: 0 / 84