Submission #789224

#	Time	Username	Problem	Language	Result	Execution time	Memory
789224		ymm	Prize (CEOI22_prize)	C++17	100 / 100	2519 ms	561004 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;


struct tree {
	int n;
	int rt;
	vector<vector<int>> A;
	vector<int> pos, ord;
	static int constexpr lg = 22;
	vector<int> rmq[lg];

	void dfs(int v, int &t) {
		pos[v] = ord.size();
		ord.push_back(v);
		for (int u : A[v]) {
			dfs(u, t);
			ord.push_back(v);
		}
	}

	int mn(int v, int u) const { return pos[v] < pos[u]? v: u; }

	void rmqmake() {
		rmq[0] = ord;
		int n = ord.size();
		Loop (i,0,lg-1) {
			rmq[i+1].resize(ord.size());
			for (int j = 0; j+(2<<i) <= n; ++j)
				rmq[i+1][j] = mn(rmq[i][j], rmq[i][j+(1<<i)]);
		}
	}

	int lca(int v, int u) const {
		v = pos[v];
		u = pos[u];
		if (v > u)
			swap(v, u);
		int len = u-v+1;
		int k = __lg(len);
		return mn(rmq[k][v], rmq[k][u+1-(1<<k)]);
	}

	void init0(int sz) {
		n = sz;
		A.clear();
		A.resize(n);
	}
	void init1() {
		pos.resize(n);
		ord.clear();
		int dard = 0;
		dfs(rt, dard);
		rmqmake();
	}
};

void read_tree(tree &t) {
	Loop (i,0,t.n) {
		int p;
		scanf("%d", &p);
		--p;
		if (p < 0)
			t.rt = i;
		else
			t.A[p].push_back(i);
	}
	t.init1();
}

void dfs_ord(const tree &t, vector<int> &vec, int v)
{
	vec.push_back(v);
	for (int u : t.A[v])
		dfs_ord(t, vec, u);
}

vector<int> dis_from_root(const tree &t, const vector<int> &ord, const vector<pii> &res)
{
	vector<int> ans(t.n);
	int dis = 0;
	Loop (i,0,ord.size()-1) {
		dis -= res[i].first;
		ans[t.lca(ord[i], ord[i+1])] = dis;
		dis += res[i].second;
		ans[ord[i+1]] = dis;
	}
	//Loop (i,p,ord.size()-1) {
	//	dis -= res[i].first;
	//	ans[t.lca(ord[i], ord[i+1])] = dis;
	//	dis += res[i].second;
	//	ans[ord[i+1]] = dis;
	//}
	//dis = 0;
	//LoopR (i,0,p) {
	//	dis -= res[i].second;
	//	ans[t.lca(ord[i], ord[i+1])] = dis;
	//	dis += res[i].first;
	//	ans[ord[i]] = dis;
	//}
	return ans;
}

int get_dis(const tree &t, const vector<int> &dis, int v, int u)
{
	int l = t.lca(v, u);
	return -2*dis[l] + dis[v] + dis[u];
}

int main()
{
	tree T1, T2;
	int n, k, q, t;
	scanf("%d%d%d%d", &n, &k, &q, &t);
	T1.init0(n);
	T2.init0(n);
	read_tree(T1);
	read_tree(T2);

	vector<int> tmp;
	dfs_ord(T1, tmp, T1.rt);
	tmp.resize(k);
	set<int> myset(tmp.begin(), tmp.end());
	tmp.clear();
	dfs_ord(T2, tmp, T2.rt);
	vector<int> ord;
	for (int x : tmp) {
		if (myset.count(x))
			ord.push_back(x);
	}
	for (int x : myset)
		printf("%d ", x+1);
	printf("\n");
	Loop (i,0,k-1)
		printf("? %d %d\n", ord[i]+1, ord[i+1]+1);
	printf("!\n");
	fflush(stdout);
	vector<pii> res1, res2;
	Loop (i,0,k-1) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		res1.push_back({a, b});
		res2.push_back({c, d});
	}
	vector<int> dis1, dis2;
	dis1 = dis_from_root(T1, ord, res1);
	dis2 = dis_from_root(T2, ord, res2);

	vector<pii> ans;
	while (t--) {
		int v, u;
		scanf("%d%d", &v, &u);
		--v; --u;
		int x = get_dis(T1, dis1, v, u);
		int y = get_dis(T2, dis2, v, u);
		ans.push_back({x, y});
	}
	for (auto [x, y] : ans)
		printf("%d %d\n", x, y);
	fflush(stdout);
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> dis_from_root(const tree&, const std::vector<int>&, const std::vector<std::pair<int, int> >&)':
Main.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
Main.cpp:86:2: note: in expansion of macro 'Loop'
   86 |  Loop (i,0,ord.size()-1) {
      |  ^~~~
Main.cpp: In function 'void read_tree(tree&)':
Main.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d", &p);
      |   ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |  scanf("%d%d%d%d", &n, &k, &q, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%d%d", &v, &u);
      |   ~~~~~^~~~~~~~~~~~~~~~

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