Submission #789205

#	Time	Username	Problem	Language	Result	Execution time	Memory
789205		ymm	Prize (CEOI22_prize)	C++17	0 / 100	1418 ms	521080 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;
		cin >> p;
		--p;
		if (p < 0)
			t.rt = i;
		else
			t.A[p].push_back(i);
	}
	t.init1();
}

vector<int> dis_from_root(const tree &t, const vector<int> &ord, const vector<pii> &res)
{
	int p = 0;
	while (ord[p] != t.rt)
		++p;
	vector<int> ans(t.n);
	int dis = 0;
	Loop (i,p,ord.size()-1) {
		dis -= res[i].first;
		dis += res[i].second;
		ans[ord[i+1]] = dis;
	}
	dis = 0;
	LoopR (i,0,p) {
		dis -= res[i].second;
		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()
{
	ios::sync_with_stdio(false);
	tree T1, T2;
	int n, k, q, t;
	cin >> n >> k >> q >> t;
	T1.init0(n);
	T2.init0(n);
	read_tree(T1);
	read_tree(T2);

	set<int> myset = {T1.rt, T2.rt};
	for (int i = 0; myset.size() < k; ++i)
		myset.insert(i);
	vector<int> ord(myset.begin(), myset.end());
	for (int x : myset)
		cout << x+1 << ' ';
	cout << '\n';
	Loop (i,0,k-1)
		cout << "? " << ord[i]+1 << ' ' << ord[i+1]+1 << '\n';
	cout << "!\n";
	vector<pii> res1, res2;
	Loop (i,0,k-1) {
		int a, b, c, d;
		cin >> 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);

	while (t--) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		cout << get_dis(T1, dis1, v, u) << ' ';
		cout << get_dis(T2, dis2, v, u) << '\n';
	}
}

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:82:2: note: in expansion of macro 'Loop'
   82 |  Loop (i,p,ord.size()-1) {
      |  ^~~~
Main.cpp: In function 'int main()':
Main.cpp:114:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |  for (int i = 0; myset.size() < k; ++i)
      |                  ~~~~~~~~~~~~~^~~

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