oj.uz

Submission #709154

# Submission time Handle Problem Language Result Execution time Memory
709154 2023-03-13T07:00:46 Z vjudge1 Prize (CEOI22_prize) C++17
10 / 100
 2643 ms 494912 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1353 ms 299764 KB Output is correct
2 Correct 1383 ms 301356 KB Output is correct
3 Correct 1018 ms 230836 KB Output is correct
4 Correct 992 ms 229896 KB Output is correct
5 Correct 1051 ms 232608 KB Output is correct
6 Correct 1256 ms 245832 KB Output is correct
7 Correct 1205 ms 245948 KB Output is correct
8 Correct 1232 ms 245308 KB Output is correct
9 Correct 992 ms 230728 KB Output is correct
10 Correct 1014 ms 232044 KB Output is correct
11 Correct 984 ms 229052 KB Output is correct
12 Correct 1037 ms 231732 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 173836 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1038 ms 296632 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2643 ms 490748 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2336 ms 494912 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -