Submission #1222746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222746		sleepntsheep	Prize (CEOI22_prize)	C++17	0 / 100	893 ms	190956 KiB

Main

#include <stdio.h>
#include <algorithm>



#define N 1000000

int n, k, q, t, p[N], dfn[N], dfc, nfd[N], fa[N], hd[N], e[N * 2]
, Ln[N * 2], ii, rt, hld[N], lv[N], dis[N], sz[N]
, hd2[N], e2[N * 2], Ln2[N * 2], ii2, dfn2[N], dfc2, fa2[N]
, hld2[N], lv2[N], sz2[N], V[N + N], tp, dis2[N], sta[N]
, e3[N * 2], Ln3[N * 2], ii3, hd3[N], dis3[N], cst[N * 2], lv3[N]
, dfn3[N], dfc3, sz3[N], hld3[N], fa3[N]
;

int cmp(int i, int j) {
	return dfn2[i] < dfn2[j];
}

void add(int u, int v) {
	++ii;
	e[ii] = v, Ln[ii] = hd[u];
	hd[u] = ii;
}

void add2(int u, int v) {
	++ii2;
	e2[ii2] = v, Ln2[ii2] = hd2[u];
	hd2[u] = ii2;
}

void add3(int u, int v, int w) {
	++ii3;
	cst[ii3] = w;
	e3[ii3] = v, Ln3[ii3] = hd3[u];
	hd3[u] = ii3;
}

void dfs(int u) {
	sz[u] = 1;
	for (int v, j = hd[u]; j; j = Ln[j]) {
		v = e[j];
		if (v == fa[u]) continue;
		fa[v] = u;
		lv[v] = lv[u] + 1;
		dfs(v);
		sz[u] += sz[v];
		if (e[hd[u]]==fa[u]||sz[v] > sz[e[hd[u]]]) e[j] = e[hd[u]], e[hd[u]] = v;
	}
}

void dfs2(int u) {
	nfd[dfn[u] = dfc++] = u;
	for (int v, j = hd[u]; j; j = Ln[j]) {
		v = e[j];
		if(v==fa[u])continue;
		hld[v] = j == hd[u] ? hld[u]: v;
		dfs2(v);
	}
}

void efs(int u) {
	sz2[u] = 1;
	for (int v, j = hd2[u]; j; j = Ln2[j]) {
		v = e2[j];
		if (v == fa2[u]) continue;
		lv2[v] = lv2[u] + 1;
		fa2[v] = u;
		efs(v);
		sz2[u] += sz2[v];
		if (e2[hd2[u]]==fa2[u] || sz2[v] > sz2[e2[hd2[u]]]) e2[j] = e2[hd2[u]], e2[hd2[u]] = v;
	}
}

void efs2(int u) {
	dfn2[u] = dfc2++;
	for (int v, j = hd2[u]; j; j = Ln2[j]) {
		v = e2[j];
		if (v == fa2[u]) continue;
		hld2[v] = j == hd2[u] ? hld2[u]: v;
		efs2(v);
	}
}

void gfs(int u) {
	sz3[u] = 1;
	for (int v, j = hd3[u]; j; j = Ln3[j]) {
		v = e3[j];
		if(v==fa3[u])continue;
		lv3[v] = lv3[u] + cst[j];
		fa3[v] = u;
		gfs(v);
		sz3[u] += sz3[v];
		if (e3[hd3[u]]==fa3[u]||
				sz3[v] > sz3[e3[hd3[u]]]) e3[j] = e3[hd3[u]], e3[hd3[u]] = v;
	}
}

void gfs2(int u) {
	dfn3[u] = dfc3++;
	for (int v, j = hd3[u]; j; j = Ln3[j]) {
		v = e3[j];
		if(v==fa3[u])continue;
		hld3[v] = j == hd3[u] ? hld3[u]: v;
		gfs2(v);
	}
}

int lca(int u, int v) {
	while (hld[u] != hld[v]) {
		if (lv[hld[u]] > lv[hld[v]]) u = fa[hld[u]];
		else v = fa[hld[v]];
	}
	return dfn[u] < dfn[v] ? u: v;
}

int lca2(int u, int v) {
	while (hld2[u] != hld2[v]) {
		if (lv2[hld2[u]] > lv2[hld2[v]]) u = fa2[hld2[u]];
		else v = fa2[hld2[v]];
	}
	return dfn2[u] < dfn2[v] ? u: v;
}

int lca3(int u, int v) {
	while (hld3[u] != hld3[v]) {
		if (lv3[hld3[u]] > lv3[hld3[v]]) u = fa3[hld3[u]];
		else v = fa3[hld3[v]];
	}
	return dfn3[u] < dfn3[v] ? u: v;
}

int main() {
	scanf("%d%d%d%d", &n, &k, &q, &t);

	for (int j, i = 0; i < n; ++i) {
		scanf("%d", &j);
		if (j > -1)
			add(--j, i), add(i, j);
	}

	for (int i = 0, j; i < n; ++i) {
		scanf("%d", &j);
		if (j > -1)
			add2(--j, i), add2(i, j);
		else
			rt = i;
	}

	fa[rt] = rt;	hld[rt] = rt;
	fa2[rt] = rt; hld2[rt] = rt;
	fa3[rt] = rt; hld3[rt] = rt;
	dfs(rt);
	dfs2(rt);
	efs(rt);
	efs2(rt);

	for (int i = 0; i < k; ++i) printf("%d ", 1 + nfd[i]); puts(""), fflush(stdout);
	for (int i = 1; i < k; ++i) printf("? %d %d\n", 1 + rt, 1 + nfd[i]);

	for (int i = 0; i < k; ++i)
		V[tp++] = nfd[i];

	std::sort(V, V + tp, cmp);
	for (int i = 1; i < tp; ++i)
		printf("? %d %d\n", 1 + V[i - 1], 1 + V[i]);

	puts("!");
	fflush(stdout);

	for (int i = 1, _, __; i < k; ++i) {
		scanf("%d%d%d%d", &_, dis + nfd[i], &__, dis2 + nfd[i]);
		dis[nfd[i]]+=_;
		///printf(" dis2[%d] = %d\n",nfd[i],dis2[nfd[i]]);
		//dis2[nfd[i]] += __;
	}

	//for (int i =0;i  < n; ++i) { printf(" dis[%d] = %d\n",i,dis[i]); }

	for (int i = 1, _; i < tp; ++i) {
		int d1, d2;
		scanf("%d%d%d%d", &_, &_, &d1, &d2);
		int ca = lca2(V[i - 1], V[i]);
		//printf(" %d -> %d : %d %d\n", V[i-1],V[i],d1, d2);
		dis2[ca] = dis2[V[i]] - d2;
	}

	/* build virtual tree */
	for (int oldtp = tp, i = 1; i < oldtp; ++i)
		V[tp++] = lca2(V[i - 1], V[i]);
	std::sort(V, V + tp, cmp);
	tp = std::unique(V, V + tp) - V;

	///puts("here");
	sta[++tp] = V[0];
	for (int i = 1; i < tp; ++i) {
		while (tp > 0 && ! (dfn2[sta[tp]] <= dfn2[V[i]] &&
					dfn2[V[i]] + sz2[V[i]] <= dfn2[sta[tp]] + sz2[sta[tp]])
				)
			--tp;
		//printf(" dis2[%d] - dis2[%d] = %d - %d  = %d\n" ,V[i],sta[tp],dis2[V[i]],dis2[sta[tp]],dis2[V[i]]-dis2[sta[tp]]);
		add3(sta[tp], V[i], dis2[V[i]] - dis2[sta[tp]]);
	}
	//puts("here2");

	gfs(rt);
	gfs2(rt);

	static int q1[N], q2[N];

	for (int i = 0; i < t; ++i)
		scanf("%d%d", &q1[i], &q2[i]);
		//printf(" Got question = %d %d\n",q1[i],q2[i]);

	for (int i = 0; i < t; ++i) {
		int u, v, x, y;
		u = q1[i] - 1, v = q2[i] - 1;
	//printf(" u, v = %d %d\n",u,v);
		x = dis[u] + dis[v] - 2 * dis[lca(u, v)];
		y = lv3[u] + lv3[v] - 2 * lv3[lca3(u, v)];
		printf("%d %d\n", x, y);
	}
	fflush(stdout);

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf("%d%d%d%d", &n, &k, &q, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:137:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |                 scanf("%d", &j);
      |                 ~~~~~^~~~~~~~~~
Main.cpp:143:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |                 scanf("%d", &j);
      |                 ~~~~~^~~~~~~~~~
Main.cpp:172:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |                 scanf("%d%d%d%d", &_, dis + nfd[i], &__, dis2 + nfd[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:182:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |                 scanf("%d%d%d%d", &_, &_, &d1, &d2);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:212:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |                 scanf("%d%d", &q1[i], &q2[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24