oj.uz

Submission #652553

# Submission time Handle Problem Language Result Execution time Memory
652553 2022-10-23T05:55:23 Z blue Prize (CEOI22_prize) C++17
0 / 100
 1074 ms 182336 KB 
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())

int N, K, Q, T;

const int mx = 500'000;
const int lg = 4;

int p[2][1+mx];
vi children[2][1+mx];
int rt[2];

vvi dfsorder(2, vi(1, 0));
vvi dfsind(2, vi(1+mx, 0));
vi ct(2, 0);
vvi depth(2, vi(1+mx, 0));
int anc[2][1 + mx][1 + lg];

void dfs(int t, int u)
{
	ct[t]++;
	dfsind[t][u] = ct[t];
	dfsorder[t].push_back(u);

	for(int v : children[t][u])
	{
		depth[t][v] = depth[t][u] + 1;

		dfs(t, v);
	}
}

int lca(int t, int u, int v)
{
	if(depth[t][u] > depth[t][v])
		swap(u, v);

	for(int e = lg; e >= 0; e--)
	{
		if((1 << e) & (depth[t][v] - depth[t][u]))
			v = anc[t][v][e];
	}

	if(u == v)
		return u;

	for(int e = lg; e >= 0; e--)
	{
		if(anc[t][u][e] != anc[t][v][e])
		{
			u = anc[t][u][e];
			v = anc[t][v][e];
		}
	}

	return anc[t][u][0];
}


vi lst[2];

int gt;




vpii edge[2][1 + mx];

int distrt[2][1 + mx];


int main()
{
	cin >> N >> K >> Q >> T;

	for(int t = 0; t < 2; t++)
	{
		for(int i = 1; i <= N; i++)
		{
			cin >> p[t][i];
		}

		rt[t] = 1;
		while(p[t][rt[t]] != -1)
			rt[t]++;

		for(int i = 1; i <= N; i++)
		{
			if(i == rt[t])
				continue;

			children[t][p[t][i]].push_back(i);
		}

		dfs(t, rt[t]);
	}

	for(int i = 1; i <= K; i++)
		cout << i << ' ';
	cout << '\n';
	cout.flush();





	for(int t = 0; t <= 1; t++)
	{
		for(int i = 1; i <= K; i++)
			lst[t].push_back(i);

		gt = t;

		sort(lst[t].begin(), lst[t].end(), [] (int u, int v)
		{
			return dfsind[gt][u] < dfsind[gt][v];
		});

		for(int i = 0; i+1 < K; i++)
		{
			cout << "? " << lst[t][i] << ' ' << lst[t][i+1] << '\n';
		}
	}

	cout << "!\n";
	cout.flush();


	for(int t = 0; t <= 1; t++)
	{
		for(int i = 1; i <= N; i++)
			anc[t][i][0] = p[t][i];

		anc[t][rt[t]][0] = rt[t];

		for(int e = 1; e <= lg; e++)
			for(int i = 1; i <= N; i++)
				anc[t][i][e] = anc[t][ anc[t][i][e-1] ][e-1];
	}






	for(int t = 0; t <= 1; t++)
	{
		vi lcv, dav, dbv;
		for(int i = 0; i+1 < K; i++)
		{
			int jnk, da, db;
			if(t == 0)
			{
				cin >> da >> db >> jnk >> jnk;
			}
			else
			{
				cin >> jnk >> jnk >> da >> db;
			}

			int lc = lca(t, lst[t][i], lst[t][i+1]);

			lcv.push_back(lc);
			dav.push_back(da);
			dbv.push_back(db);

			edge[t][lc].push_back({lst[t][i], da});
			edge[t][lc].push_back({lst[t][i+1], db});

			// cerr << t << ' ' << lc << " -> " << lst[t][i] << ' ' << da << " , " << lst[t][i+1] << ' ' << db << '\n';
			// lst[t].push_back(lc);
		}

		for(int i = 1; i < K-1; i++)
		{
			if(lcv[i] == lcv[i-1])
				continue;

			// cerr << i << " : " << lcv[i-1] << ' ' << lcv[i] << " a \n";
			// cerr << dbv[i-1] << ' ' << dav[i] << '\n';

			if(dbv[i-1] >= dav[i])
				edge[t][lcv[i-1]].push_back({lcv[i], dbv[i-1] - dav[i]});
			else
				edge[t][lcv[i]].push_back({lcv[i-1], dav[i] - dbv[i-1]});
		}
		// cerr << "read\n";

		// gt = t;

		// sort(lst[t].begin(), lst[t].end(), [] (int u, int v)
		// {
		// 	return dfsind[gt][u] < dfsind[gt][v];
		// });



		for(int i = 1; i <= N; i++)
			distrt[t][i] = 0;


		for(int u : dfsorder[t])
		{
			if(u == 0)
				continue;

			for(pii vp : edge[t][u])
			{
				int v = vp.first;
				int w = vp.second;

				distrt[t][v] = max(distrt[t][v], distrt[t][u] + w);
			}
		}
	}

	// for(int t = 0; t <= 1; t++)
	// {
	// 	for(int i = 1; i <= N; i++)
	// 		cerr << distrt[t][i] << ' ';
	// 	cerr << '\n';
	// }


	for(int t = 1; t <= T; t++)
	{
		int p, q;
		cin >> p >> q;

		int l0 = lca(0, p, q);
		int l1 = lca(1, p, q);

		// cerr << l0 << " | " << l1 << '\n';
		// cerr << distrt[0][p] << ' ' << distrt[0][q] << ' ' << distrt[0][l0] << '\n';

		ll ans0 = distrt[0][p] + distrt[0][q] - 2*distrt[0][l0];
		ll ans1 = distrt[1][p] + distrt[1][q] - 2*distrt[1][l1];

		cout << ans0 << ' ' << ans1 << '\n';
	}

	cout.flush();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 997 ms 156644 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 159788 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 737 ms 151396 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 182328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 605 ms 182336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -