oj.uz

답안 #727331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727331 2023-04-20T12:05:54 Z amunduzbaev Prize (CEOI22_prize) C++17
100 / 100
 3180 ms 551112 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

const int N = 1e6 + 5;
vector<int> G[2][N];
int tin[2][N], tout[2][N], par[2][N][20];
int d[2][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q, T; cin >> n >> k >> q >> T;
	int R[2] {};
	for(int i=1;i<=n;i++){
		int p; cin >> p;
		if(~p){
			G[0][p].push_back(i);
		} else {
			R[0] = i;
		}
	}
	for(int i=1;i<=n;i++){
		int p; cin >> p;
		if(~p){
			G[1][p].push_back(i);
		} else {
			R[1] = i;
		}
	}
	
	for(int c=0;c<2;c++){
		int t = 0;
		tout[c][0] = N;
		function<void(int)> dfs = [&](int u){
			tin[c][u] = ++t;
			for(int j=1;j<20;j++){
				par[c][u][j] = par[c][par[c][u][j-1]][j-1];
			}
			for(auto x : G[c][u]){
				par[c][x][0] = u;
				dfs(x);
			}
			tout[c][u] = t;
		};
		dfs(R[c]);
	}
	
	vector<int> p;
	function<void(int)> dfs = [&](int u){
		if(tin[0][u] <= k){
			p.push_back(u);
		}
		for(auto x : G[0][u]){
			dfs(x);
		}
	};
	dfs(R[0]);
	for(auto x : p){
		cout<<x<<" ";
	} cout<<endl;
	
	auto is = [&](int t, int a, int b){
		return (tin[t][a] <= tin[t][b] && tin[t][b] <= tout[t][a]);
	};
	
	auto Lca = [&](int t, int a, int b){
		if(is(t, a, b)) return a;
		if(is(t, b, a)) return b;
		for(int j=19;~j;j--){
			if(!is(t, par[t][a][j], b)) a = par[t][a][j];
		}
		return par[t][a][0];
	};
	
	sort(p.begin(), p.end(), [&](int a, int b){
		return tin[1][a] < tin[1][b];
	});
	
	for(int i=1;i<k;i++){
		cout<<"? "<<p[i-1]<<" "<<p[i]<<endl;
	}
	cout<<"! "<<endl;
	
	for(int i=1;i<k;i++){
		int dc, dd, da, db; cin >> dc >> dd >> da >> db;
		int lca = Lca(1, p[i-1], p[i]);
		d[1][lca] = d[1][p[i-1]] - da;
		d[1][p[i]] = d[1][lca] + db;
		d[0][p[i]] = d[0][p[i-1]] - dc + dd;
	}
	
	vector<ar<int, 2>> Q;
	for(int i=0;i<T;i++){
		int a, b; cin >> a >> b;
		Q.push_back({a, b});
	}
	
	for(auto [a, b] : Q){
		for(int c=0;c<2;c++){
			int lca = Lca(c, a, b);
			cout<<d[c][a] + d[c][b] - d[c][lca] * 2<<" ";
		}
		cout<<endl;
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1608 ms 300520 KB Output is correct
2 Correct 1918 ms 300724 KB Output is correct
3 Correct 1116 ms 248872 KB Output is correct
4 Correct 1234 ms 248796 KB Output is correct
5 Correct 1074 ms 249052 KB Output is correct
6 Correct 1595 ms 258880 KB Output is correct
7 Correct 1579 ms 258764 KB Output is correct
8 Correct 1575 ms 258804 KB Output is correct
9 Correct 1057 ms 248844 KB Output is correct
10 Correct 1060 ms 248944 KB Output is correct
11 Correct 1078 ms 248624 KB Output is correct
12 Correct 1076 ms 248932 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1628 ms 300748 KB Output is correct
2 Correct 1602 ms 300296 KB Output is correct
3 Correct 1076 ms 248800 KB Output is correct
4 Correct 1144 ms 249084 KB Output is correct
5 Correct 1108 ms 248956 KB Output is correct
6 Correct 1574 ms 258616 KB Output is correct
7 Correct 1635 ms 258852 KB Output is correct
8 Correct 1701 ms 259004 KB Output is correct
9 Correct 1659 ms 257732 KB Output is correct
10 Correct 1404 ms 257572 KB Output is correct
11 Correct 1357 ms 257360 KB Output is correct
12 Correct 1414 ms 257592 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1413 ms 292656 KB Output is correct
2 Correct 1383 ms 292572 KB Output is correct
3 Correct 833 ms 241372 KB Output is correct
4 Correct 822 ms 241424 KB Output is correct
5 Correct 844 ms 241268 KB Output is correct
6 Correct 1125 ms 251236 KB Output is correct
7 Correct 1076 ms 251384 KB Output is correct
8 Correct 1082 ms 251472 KB Output is correct
9 Correct 964 ms 250028 KB Output is correct
10 Correct 992 ms 249880 KB Output is correct
11 Correct 934 ms 249852 KB Output is correct
12 Correct 992 ms 249784 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3104 ms 541000 KB Output is correct
2 Correct 2960 ms 541276 KB Output is correct
3 Correct 1876 ms 438940 KB Output is correct
4 Correct 1863 ms 438840 KB Output is correct
5 Correct 1855 ms 438880 KB Output is correct
6 Correct 2999 ms 459056 KB Output is correct
7 Correct 2595 ms 459184 KB Output is correct
8 Correct 2622 ms 459000 KB Output is correct
9 Correct 2194 ms 456264 KB Output is correct
10 Correct 2286 ms 456260 KB Output is correct
11 Correct 2311 ms 455988 KB Output is correct
12 Correct 2227 ms 456216 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3145 ms 551104 KB Output is correct
2 Correct 3180 ms 551112 KB Output is correct
3 Correct 1993 ms 447548 KB Output is correct
4 Correct 2462 ms 447764 KB Output is correct
5 Correct 1948 ms 447352 KB Output is correct
6 Correct 3021 ms 467672 KB Output is correct
7 Correct 2872 ms 467276 KB Output is correct
8 Correct 3002 ms 467568 KB Output is correct
9 Correct 2591 ms 464644 KB Output is correct
10 Correct 2549 ms 464512 KB Output is correct
11 Correct 2511 ms 464576 KB Output is correct
12 Correct 2641 ms 464708 KB Output is correct