oj.uz

Submission #792460

# Submission time Handle Problem Language Result Execution time Memory
792460 2023-07-25T05:10:33 Z ono_de206 Prize (CEOI22_prize) C++14
100 / 100
 3461 ms 473460 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

struct tree {
	int n, lg, t;
	vector<int> dep, in, out;
	vector<vector<int>> jump, g;
	bool did;

	tree(int _n) : n(_n) {
		g.resize(n + 1);
		in.resize(n + 1);
		out.resize(n + 1);
		dep.resize(n + 1);
		did = 0;
		lg = t = 0;
		while((1 << lg) <= n) lg++;
		jump.resize(n + 1, vector<int>(lg));
	}

	void build(int to = 1, int fr = 0) {
		dep[to] = dep[fr] + 1;
		jump[to][0] = fr;
		in[to] = ++t;
		for(int x : g[to]) {
			if(x == fr) continue;
			build(x, to);
		}
		out[to] = t;
	}

	void add(int x, int y) {
		g[x].pb(y);
		g[y].pb(x);
	}

	void buildLCA() {
		if(did) return;
		did = 1;
		for(int j = 1; j < lg; j++) {
			for(int i = 1; i <= n; i++) {
				jump[i][j] = jump[jump[i][j - 1]][j - 1];
			}
		}
	}

	int lca(int x, int y) {
		if(dep[x] < dep[y]) swap(x, y);
		int dff = dep[x] - dep[y];
		for(int i = 0; i < lg; i++) {
			if((dff >> i) & 1) x = jump[x][i];
		}
		if(x == y) return x;
		for(int i = lg - 1; i >= 0; i--) {
			if(jump[x][i] != jump[y][i]) {
				x = jump[x][i];
				y = jump[y][i];
			}
		}
		return jump[x][0];
	}

	int distance(int x, int y) {
		return dep[x] + dep[y] - dep[lca(x, y)] * 2;
	}

	bool isAnc(int x, int y) {
		return in[x] <= in[y] && out[x] >= out[y]; 
	}

	bool isOn(int x, int y, int z) {
		int p = lca(x, y);
		if(dep[p] > dep[z]) return 0;
		return (isAnc(z, x) || isAnc(z, y));
	}

	~tree() {
		jump.clear();
		dep.clear();
		g.clear();
		in.clear();
		out.clear();
	}
};

const int mxn = 1e6 + 10;
int dis1[mxn], dis2[mxn];
bool vis[mxn];
vector<pair<int, int>> adj1[mxn], adj2[mxn];

void dfs1(int to, int dis) {
	dis1[to] = dis;
	vis[to] = 1;
	for(auto it : adj1[to]) {
		if(vis[it.ff]) continue;
		dfs1(it.ff, dis + it.ss);
	}
}

void dfs2(int to, int dis) {
	dis2[to] = dis;
	vis[to] = 1;
	for(auto it : adj2[to]) {
		if(vis[it.ff]) continue;
		dfs2(it.ff, dis + it.ss);
	}
}

int main() {
	fast;
	int n, k, q, t; cin >> n >> k >> q >> t;
	tree tr1(n), tr2(n);
	int root1, root2;
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		if(~x) tr1.add(x, i);
		else root1 = i;
	}
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		if(~x) tr2.add(x, i);
		else root2 = i;
	}

	tr1.build(root1); tr1.buildLCA();
	tr2.build(root2); tr2.buildLCA();

	vector<int> ks(n);
	iota(all(ks), 1);
	sort(all(ks), [&](int x, int y) {
		return tr1.in[x] < tr1.in[y];
	});
	ks.resize(k);
	sort(all(ks), [&](int x, int y) {
		return tr2.in[x] < tr2.in[y];
	});

	for(int i = 0; i < k; i++) {
		cout << ks[i] << ' ';
	}
	cout << endl;
	for(int i = 0; i + 1 < k; i++) {
		cout << "? " << ks[i] << ' ' << ks[i + 1] << endl;
	}
	cout << "!" << endl;
	for(int i = 0; i + 1 < k; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int lc1 = tr1.lca(ks[i], ks[i + 1]);
		int lc2 = tr2.lca(ks[i], ks[i + 1]);
		adj1[ks[i]].eb(lc1, -a);
		adj1[lc1].eb(ks[i + 1], b);
		adj2[ks[i]].eb(lc2, -c);
		adj2[lc2].eb(ks[i + 1], d);
	}
	dfs1(ks[0], 0);
	for(int i = 0; i < k; i++) {
		vis[ks[i]] = 0;
	}
	dfs2(ks[0], 0);
	vector<pair<int, int>> ans;
	for(int i = 0; i < t; i++) {
		int x, y; cin >> x >> y;
		ans.eb(dis1[x] + dis1[y] - dis1[tr1.lca(x, y)] * 2, dis2[x] + dis2[y] - dis2[tr2.lca(x, y)] * 2);
	}
	for(auto &it : ans) {
		cout << it << endl;
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:170:11: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  170 |  tr1.build(root1); tr1.buildLCA();
      |  ~~~~~~~~~^~~~~~~
Main.cpp:171:11: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  171 |  tr2.build(root2); tr2.buildLCA();
      |  ~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1842 ms 261920 KB Output is correct
2 Correct 1812 ms 263544 KB Output is correct
3 Correct 1375 ms 244996 KB Output is correct
4 Correct 1151 ms 244684 KB Output is correct
5 Correct 1193 ms 246356 KB Output is correct
6 Correct 1562 ms 247916 KB Output is correct
7 Correct 1582 ms 247948 KB Output is correct
8 Correct 1611 ms 247452 KB Output is correct
9 Correct 1116 ms 244820 KB Output is correct
10 Correct 1188 ms 246028 KB Output is correct
11 Correct 1077 ms 243828 KB Output is correct
12 Correct 1185 ms 245660 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1795 ms 263840 KB Output is correct
2 Correct 1651 ms 261260 KB Output is correct
3 Correct 1376 ms 245840 KB Output is correct
4 Correct 1617 ms 247596 KB Output is correct
5 Correct 1535 ms 246224 KB Output is correct
6 Correct 1790 ms 247232 KB Output is correct
7 Correct 1823 ms 249564 KB Output is correct
8 Correct 1831 ms 249692 KB Output is correct
9 Correct 1633 ms 250480 KB Output is correct
10 Correct 1686 ms 251040 KB Output is correct
11 Correct 1517 ms 248420 KB Output is correct
12 Correct 1684 ms 250884 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 254652 KB Output is correct
2 Correct 1236 ms 254708 KB Output is correct
3 Correct 857 ms 237028 KB Output is correct
4 Correct 885 ms 237088 KB Output is correct
5 Correct 923 ms 236964 KB Output is correct
6 Correct 1142 ms 239684 KB Output is correct
7 Correct 1101 ms 239592 KB Output is correct
8 Correct 1183 ms 239780 KB Output is correct
9 Correct 993 ms 240276 KB Output is correct
10 Correct 982 ms 240084 KB Output is correct
11 Correct 1149 ms 240104 KB Output is correct
12 Correct 1125 ms 240168 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3395 ms 464464 KB Output is correct
2 Correct 3403 ms 464628 KB Output is correct
3 Correct 2300 ms 429288 KB Output is correct
4 Correct 2213 ms 429172 KB Output is correct
5 Correct 2274 ms 429228 KB Output is correct
6 Correct 3111 ms 434448 KB Output is correct
7 Correct 2987 ms 434556 KB Output is correct
8 Correct 2937 ms 434448 KB Output is correct
9 Correct 2433 ms 435404 KB Output is correct
10 Correct 2682 ms 435344 KB Output is correct
11 Correct 2550 ms 435308 KB Output is correct
12 Correct 2457 ms 435376 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3402 ms 473460 KB Output is correct
2 Correct 3302 ms 473192 KB Output is correct
3 Correct 2499 ms 436772 KB Output is correct
4 Correct 2593 ms 439748 KB Output is correct
5 Correct 2544 ms 436344 KB Output is correct
6 Correct 3420 ms 444768 KB Output is correct
7 Correct 3273 ms 441564 KB Output is correct
8 Correct 3461 ms 443572 KB Output is correct
9 Correct 3031 ms 444040 KB Output is correct
10 Correct 3097 ms 443204 KB Output is correct
11 Correct 3041 ms 443284 KB Output is correct
12 Correct 3176 ms 444916 KB Output is correct