oj.uz

Submission #792474

# Submission time Handle Problem Language Result Execution time Memory
792474 2023-07-25T05:18:46 Z ono_de206 Prize (CEOI22_prize) C++14
100 / 100
 3399 ms 470040 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;
	for(int i = 1; i <= n; i++) {
		if(tr1.in[i] <= k) ks.pb(i);
	}
	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 1579 ms 260360 KB Output is correct
2 Correct 1711 ms 262000 KB Output is correct
3 Correct 1091 ms 243328 KB Output is correct
4 Correct 1082 ms 243016 KB Output is correct
5 Correct 1129 ms 244832 KB Output is correct
6 Correct 1586 ms 246356 KB Output is correct
7 Correct 1493 ms 246268 KB Output is correct
8 Correct 1503 ms 245784 KB Output is correct
9 Correct 1132 ms 243136 KB Output is correct
10 Correct 1167 ms 244436 KB Output is correct
11 Correct 1094 ms 242116 KB Output is correct
12 Correct 1120 ms 244076 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1677 ms 262324 KB Output is correct
2 Correct 1550 ms 259476 KB Output is correct
3 Correct 1370 ms 244040 KB Output is correct
4 Correct 1387 ms 246000 KB Output is correct
5 Correct 1277 ms 244548 KB Output is correct
6 Correct 1606 ms 245648 KB Output is correct
7 Correct 1818 ms 247924 KB Output is correct
8 Correct 1844 ms 248156 KB Output is correct
9 Correct 1554 ms 248940 KB Output is correct
10 Correct 1626 ms 249564 KB Output is correct
11 Correct 1413 ms 246688 KB Output is correct
12 Correct 1578 ms 249408 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 252696 KB Output is correct
2 Correct 1183 ms 252696 KB Output is correct
3 Correct 797 ms 235132 KB Output is correct
4 Correct 824 ms 235164 KB Output is correct
5 Correct 805 ms 235104 KB Output is correct
6 Correct 1108 ms 237748 KB Output is correct
7 Correct 1181 ms 237632 KB Output is correct
8 Correct 1229 ms 237760 KB Output is correct
9 Correct 1002 ms 238224 KB Output is correct
10 Correct 1088 ms 238080 KB Output is correct
11 Correct 1020 ms 238120 KB Output is correct
12 Correct 1068 ms 238216 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2815 ms 460568 KB Output is correct
2 Correct 2995 ms 460752 KB Output is correct
3 Correct 2003 ms 425344 KB Output is correct
4 Correct 1996 ms 425276 KB Output is correct
5 Correct 2155 ms 425336 KB Output is correct
6 Correct 3327 ms 430540 KB Output is correct
7 Correct 2916 ms 430716 KB Output is correct
8 Correct 2871 ms 430560 KB Output is correct
9 Correct 2453 ms 431472 KB Output is correct
10 Correct 2508 ms 431512 KB Output is correct
11 Correct 2470 ms 431408 KB Output is correct
12 Correct 2394 ms 431384 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3399 ms 470040 KB Output is correct
2 Correct 3389 ms 469568 KB Output is correct
3 Correct 2412 ms 433148 KB Output is correct
4 Correct 2571 ms 436236 KB Output is correct
5 Correct 2327 ms 432636 KB Output is correct
6 Correct 3275 ms 441524 KB Output is correct
7 Correct 3141 ms 437820 KB Output is correct
8 Correct 3248 ms 439804 KB Output is correct
9 Correct 2907 ms 440428 KB Output is correct
10 Correct 2938 ms 439712 KB Output is correct
11 Correct 2857 ms 439820 KB Output is correct
12 Correct 2913 ms 441228 KB Output is correct