Submission #132161

#	Time	Username	Problem	Language	Result	Execution time	Memory
132161		onjo0127	Construction of Highway (JOI18_construction)	C++11	100 / 100	1018 ms	18332 KiB

construction

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct maxseg {
	vector<int> T;
	void upd(int idx, int s, int e, int p, int v) {
		if(p < s || e < p) return;
		if(s == e) {
			T[idx] = v;
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, p, v);
		upd(idx*2+1, m+1, e, p, v);
		T[idx] = max(T[idx*2], T[idx*2+1]);
	}
	int get(int idx, int s, int e, int l, int r) {
		if(r < s || e < l) return 0;
		if(l <= s && e <= r) return T[idx];
		int m = s+e >> 1;
		return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
	}
	maxseg(int N) {
		T.resize(4*N);
	}
};

const int _N = 100009;
int A[_N], B[_N], C[_N], in[_N], ou[_N], t, d[_N], r[_N];
vector<int> adj[_N], CS;
long long F[_N];

void upd(int x, int y) {
	for(int i=x; i<=(int)CS.size(); i+=(i&-i)) F[i] += y;
}
long long get(int x) {
	long long ret = 0;
	for(int i=x; i>=1; i-=(i&-i)) ret += F[i];
	return ret;
}

void dfs(int x, int p, int d) {
	in[x] = ++t; ::d[x] = d;
	for(auto& it: adj[x]) dfs(it, x, d+1);
	ou[x] = t;
}

int main() {
	int N; scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d",&C[i]);
		CS.push_back(C[i]);
	}
	sort(CS.begin(), CS.end());
	CS.resize(unique(CS.begin(), CS.end()) - CS.begin());
	for(int i=1; i<=N; i++) C[i] = lower_bound(CS.begin(), CS.end(), C[i]) - CS.begin() + 1;

	for(int i=1; i<N; i++) {
		scanf("%d%d",&A[i],&B[i]);
		adj[A[i]].push_back(B[i]);
	}
	dfs(1, 1, 1);
	maxseg seg(N);
	B[0] = 1; r[0] = 0;
	for(int i=1; i<N; i++) {
		int now = A[i], ni = seg.get(1, 1, N, in[now], ou[now]);
		vector<pii> S = {{ni, now}};
		while(1) {
			now = r[seg.get(1, 1, N, in[now], ou[now])];
			if(now == 0) break;
			ni = seg.get(1, 1, N, in[now], ou[now]);
			S.push_back({ni, now});
		}
		long long ans = 0;
		for(auto& it: S) {
			ans += 1LL * (d[it.second] - d[r[it.first]]) * get(C[B[it.first]] - 1);
			upd(C[B[it.first]], d[it.second] - d[r[it.first]]);
		}
		for(auto& it: S) {
			upd(C[B[it.first]], d[r[it.first]] - d[it.second]);
			r[it.first] = it.second;
		}
		r[i] = 0;
		seg.upd(1, 1, N, in[B[i]], i);
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In member function 'void maxseg::upd(int, int, int, int, int)':
construction.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
construction.cpp: In member function 'int maxseg::get(int, int, int, int, int)':
construction.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
construction.cpp: In function 'int main()':
construction.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
construction.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&C[i]);
   ~~~~~^~~~~~~~~~~~
construction.cpp:60: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