Submission #709154

#	Time	Username	Problem	Language	Result	Execution time	Memory
709154		vjudge1	Prize (CEOI22_prize)	C++17	10 / 100	2643 ms	494912 KiB

Main

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define nl "\n"

using namespace std;

const int N = (int)1e6 + 7;
const int inf = (int)1e9 + 7;

int n, k, q, t, d[N];

struct Tree {
	int root;
	vector<int> g[N];
};
Tree t1, t2;

vector<int> con;
vector<pair<int, int > > edges;
int timer = 1;
unordered_map<int, int> W[N];
    
vector<int> ask() {
	vector<int> v;
	for(int i = 0; i < 4; ++i) {
		int x;
		cin >> x;
		v.pb(x);	
	}
	return v;
}

void dfs(int v, int pr) {
	for(auto to : t1.g[v]) {
		if(to == pr) continue;
		if(timer < k) {
			timer++;
			con.pb(to);
			edges.pb({v, to});
		}
		dfs(to, v);
	}
}

int tin[N], tout[N], up[N][20];

void calc(int v, int pr) {
	tin[v] = ++timer;
	up[v][0] = pr;
	for(int i = 1; i <= 19; ++i) {
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for(auto to : t1.g[v]) {
		if(to == pr) continue;
		d[to] = d[v] + W[v][to];
		calc(to, v);
	}               
	tout[v] = ++timer;
}

bool is_parent(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
	if(is_parent(u, v)) return u;
	if(is_parent(v, u)) return v;
	for(int i = 19; i >= 0; --i) {
		if(!is_parent(up[u][i], v)) {
			u = up[u][i];
		}
	}
	return up[u][0];
}

void solve1() {
	con.pb(t1.root);
	dfs(t1.root, -1);
	for(int i = 0; i < k; ++i) cout << con[i] << ' ';
	cout << endl;
	for(int i = 0; i < q; ++i) {
		cout << "? " << edges[i].x << ' ' << edges[i].y << endl;
	}
	cout << "!" << endl;
	for(int i = 0; i < q; ++i) {
		vector<int> cur = ask();
		int dist = cur[0] + cur[1];
		W[edges[i].x][edges[i].y] = W[edges[i].y][edges[i].x] = dist;
	}
	timer = 0;
	calc(t1.root, t1.root);
	vector<pair<int, int> > e;
	for(int i = 0; i < t; ++i) {
		int u, v;
		cin >> u >> v;
		e.pb({u, v});
	}	
	for(int i = 0; i < t; ++i) {
		int k = lca(e[i].x, e[i].y);
		int ans = d[e[i].x] - 2 * d[k] + d[e[i].y];
		cout << ans << ' ' << ans << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cin >> n >> k >> q >> t;
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		if(x != -1) {
			t1.g[i].pb(x);
			t1.g[x].pb(i);				
		} else {
			t1.root = i;
		}	
	}
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		if(x != -1) {
			t2.g[i].pb(x);
			t2.g[x].pb(i);				
		} else {
			t2.root = i;
		}	
	}
	solve1();
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24