oj.uz

Submission #789209

# Submission time Handle Problem Language Result Execution time Memory
789209 2023-07-21T07:43:48 Z ymm Prize (CEOI22_prize) C++17
0 / 100
 1662 ms 521096 KB 
#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()
{
	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";
	cout.flush();
	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

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:113:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |  for (int i = 0; myset.size() < k; ++i)
      |                  ~~~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 796 ms 261608 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 876 ms 264312 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 718 ms 256956 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1499 ms 513624 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1662 ms 521096 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -