oj.uz

Submission #789224

# Submission time Handle Problem Language Result Execution time Memory
789224 2023-07-21T08:17:32 Z ymm Prize (CEOI22_prize) C++17
100 / 100
 2519 ms 561004 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;
		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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1133 ms 282788 KB Output is correct
2 Correct 1127 ms 285016 KB Output is correct
3 Correct 686 ms 237052 KB Output is correct
4 Correct 740 ms 236572 KB Output is correct
5 Correct 738 ms 238312 KB Output is correct
6 Correct 925 ms 247640 KB Output is correct
7 Correct 871 ms 247596 KB Output is correct
8 Correct 964 ms 247224 KB Output is correct
9 Correct 722 ms 236968 KB Output is correct
10 Correct 761 ms 238016 KB Output is correct
11 Correct 778 ms 235712 KB Output is correct
12 Correct 803 ms 237752 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 284852 KB Output is correct
2 Correct 1103 ms 281924 KB Output is correct
3 Correct 677 ms 236976 KB Output is correct
4 Correct 834 ms 238484 KB Output is correct
5 Correct 716 ms 237508 KB Output is correct
6 Correct 927 ms 245672 KB Output is correct
7 Correct 904 ms 247852 KB Output is correct
8 Correct 918 ms 248204 KB Output is correct
9 Correct 868 ms 246264 KB Output is correct
10 Correct 856 ms 246836 KB Output is correct
11 Correct 804 ms 244148 KB Output is correct
12 Correct 913 ms 246644 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 277176 KB Output is correct
2 Correct 924 ms 277212 KB Output is correct
3 Correct 575 ms 230808 KB Output is correct
4 Correct 576 ms 230804 KB Output is correct
5 Correct 548 ms 230840 KB Output is correct
6 Correct 761 ms 240592 KB Output is correct
7 Correct 738 ms 240748 KB Output is correct
8 Correct 711 ms 240604 KB Output is correct
9 Correct 687 ms 238604 KB Output is correct
10 Correct 670 ms 238676 KB Output is correct
11 Correct 664 ms 238648 KB Output is correct
12 Correct 684 ms 238620 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2519 ms 554316 KB Output is correct
2 Correct 2183 ms 554328 KB Output is correct
3 Correct 1382 ms 461504 KB Output is correct
4 Correct 1343 ms 461580 KB Output is correct
5 Correct 1336 ms 461380 KB Output is correct
6 Correct 1789 ms 481356 KB Output is correct
7 Correct 1836 ms 481332 KB Output is correct
8 Correct 1806 ms 481284 KB Output is correct
9 Correct 1586 ms 477064 KB Output is correct
10 Correct 1575 ms 476984 KB Output is correct
11 Correct 1674 ms 477120 KB Output is correct
12 Correct 1590 ms 477060 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2448 ms 561004 KB Output is correct
2 Correct 2376 ms 560664 KB Output is correct
3 Correct 1719 ms 465924 KB Output is correct
4 Correct 1913 ms 468660 KB Output is correct
5 Correct 1780 ms 465368 KB Output is correct
6 Correct 2143 ms 488180 KB Output is correct
7 Correct 2060 ms 485204 KB Output is correct
8 Correct 2157 ms 487364 KB Output is correct
9 Correct 1877 ms 482964 KB Output is correct
10 Correct 1822 ms 481812 KB Output is correct
11 Correct 1807 ms 481836 KB Output is correct
12 Correct 1811 ms 483488 KB Output is correct