oj.uz

답안 #789210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789210 2023-07-21T07:48:27 Z ymm Prize (CEOI22_prize) C++17
0 / 100
 1589 ms 521884 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();
}

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;
	scanf("%d%d%d%d", &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)
		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: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)
      |                  ~~~~~~~~~~~~~^~~
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:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d%d%d%d", &n, &k, &q, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   scanf("%d%d", &v, &u);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 740 ms 263188 KB Output is correct
2 Correct 741 ms 265308 KB Output is correct
3 Runtime error 520 ms 234624 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 752 ms 265160 KB Output is correct
2 Correct 727 ms 262352 KB Output is correct
3 Runtime error 505 ms 234636 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 660 ms 257832 KB Output is correct
2 Correct 627 ms 257852 KB Output is correct
3 Runtime error 438 ms 228884 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1586 ms 515572 KB Output is correct
2 Correct 1480 ms 515652 KB Output is correct
3 Runtime error 1074 ms 457488 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1589 ms 521884 KB Output is correct
2 Correct 1585 ms 521572 KB Output is correct
3 Runtime error 1134 ms 461688 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -