Submission #56432

#	Time	Username	Problem	Language	Result	Execution time	Memory
56432		ics0503	Construction of Highway (JOI18_construction)	C++17	100 / 100	742 ms	26172 KiB

construction

#include<stdio.h>
#include<vector>
using namespace std;
int par[121212][20], num[121212], S[121212], E[121212], cnt, tn, depth[121212], A[121212], B[121212], C[121212], CSD[121212];
vector<int>edge[121212];
struct xy { int x, y; }tree[313131], temp[121212];
xy max(xy a, xy b) { if (a.x > b.x)return a; return b; }
void insert_g(int w, xy g) { for (int i = w + tn; i > 0; i /= 2)tree[i] = max(tree[i], g); }
int search_g(int s, int e) {
	s += tn; e += tn; xy res = { -1,0 };
	while (s <= e) {
		if ((s & 1) == 1)res = max(res, tree[s++]);
		if ((e & 1) == 0)res = max(res, tree[e--]);
		s>>=1; e>>=1;
	}
	return res.y;
}
void dfs(int w, int bef, int dep) {
	par[w][0] = bef; depth[w] = dep;
	for (int i = 0; par[w][i] != -1; i++)par[w][i + 1] = par[par[w][i]][i];
	num[w] = S[w] = ++cnt;
	for (int i = 0; i < edge[w].size(); i++)if (edge[w][i] != bef) {
		dfs(edge[w][i], w, dep + 1);
	}
	E[w] = cnt;
}
int get_C(int x) { return search_g(S[x], E[x]); }
int go(int a, int b) { for (int i = 0; i < 20; i++)if ((1 << i)&b)a = par[a][i]; return a; }
vector<xy>L;
long long f(int s, int e) {
	if (s == e)return 0;
	int m = (s + e) / 2, i;
	long long res = f(s, m) + f(m + 1, e);
	int p1 = s, p2 = m + 1, jw = m, S = 0;
	for (i = s; i <= m; i++) {
		while (jw + 1 <= e&&L[i].x < L[jw + 1].x)S += L[++jw].y;
		res += (long long)L[i].y * S;
	}
	for (i = s; i <= e; i++) {
		if (p1 == m + 1 || (p2 != e + 1 && L[p1].x < L[p2].x)) temp[i] = L[p2++];
		else temp[i] = L[p1++];
	}
	for (i = s; i <= e; i++) L[i] = temp[i];
	return res;
}
int main() {
	int n, i, j; scanf("%d", &n);
	for (tn = 1; tn < n + 1; tn *= 2);
	for (i = 0; i < tn * 2; i++)tree[i].x = -1;
	for (i = 1; i <= n; i++)scanf("%d", &C[i]);
	for (i = 1; i <= n; i++)for (j = 0; j < 20; j++)par[i][j] = -1;
	for (i = 1; i <= n - 1; i++) {
		int s, e; scanf("%d%d", &s, &e);
		A[i] = s; B[i] = e;
		edge[s].push_back(e); edge[e].push_back(s);
	}
	dfs(1, -1, 0);
	CSD[1] = 0; insert_g(1, { 0,1 });
	for (i = 1; i <= n - 1; i++) {
		L.clear();
		int e = B[i], now = par[e][0];
		while (now != -1) {
			int nowC = get_C(now);
			int cs = go(now, depth[now] - CSD[nowC]);
			L.push_back({ C[nowC],depth[now] - CSD[nowC] + 1 });
			CSD[nowC] = depth[now] + 1;
			now = par[cs][0];
		}
		insert_g(num[e], { i, e });
		printf("%lld\n", f(0, L.size() - 1));
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void dfs(int, int, int)':
construction.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edge[w].size(); i++)if (edge[w][i] != bef) {
                  ~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:47:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, i, j; scanf("%d", &n);
               ~~~~~^~~~~~~~~~
construction.cpp:50:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++)scanf("%d", &C[i]);
                          ~~~~~^~~~~~~~~~~~~
construction.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~

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