oj.uz

Submission #1035054

# Submission time Handle Problem Language Result Execution time Memory
1035054 2024-07-26T03:34:51 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 735460 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define pll pair<ll,ll>
#define al4 array<ll,4>
#define ai4 array<int,4>

const int mxn = 1e6+10;
const int B = 20;

struct Tree{
	vector<vector<int>> par;
	vector<int> dfn;
	vector<pii> eul;
	vector<int> dep;
	vector<vector<int>> edges;
	int pt = 0;
	Tree(){}
	void init(int n){
		pt = 0;
		dfn.clear();
		eul = vector<pii>(n);
		dep = vector<int>(n);
		edges = vector<vector<int>>(n);
		par = vector<vector<int>>(n,vector<int>(B,0));
	}
	void add_edge(int a,int b){
		edges[a].push_back(b);
	}
	void dfs(int now = 1,int fa = 1){
		eul[now].fs = ++pt;
		dfn.push_back(now);
		par[now][0] = fa;
		for(int i = 1;i<B;i++)par[now][i] = par[par[now][i-1]][i-1];
		for(auto nxt:edges[now]){
			if(nxt == par[now][0])continue;
			par[nxt][0] = now;
			dep[nxt] = dep[now]+1;
			dfs(nxt,now);
		}
		eul[now].sc = pt;
	}
	int LCA(int a,int b){
		if(dep[a]<dep[b])swap(a,b);
		int d = dep[a]-dep[b];
		for(int i = B-1;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		for(int i = B-1;i>=0;i--){
			if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
		}
		return a==b?a:par[a][0];
	}
};

Tree t1,t2,vt;
int rt1,rt2;
int N,K,Q,T;
int val1[mxn],val2[mxn];
vector<int> tar;

namespace PEKO{
	Tree re;
	Tree GO(vector<int> v,Tree& tr){
		re.init(N+1);
		sort(v.begin(),v.end(),[&](int a,int b){return tr.eul[a].fs<tr.eul[b].fs;});
		int s = v.size();
		for(int i = 1;i<s;i++){
			v.push_back(tr.LCA(v[i-1],v[i]));
		}
		sort(v.begin(),v.end(),[&](int a,int b){return tr.eul[a].fs<tr.eul[b].fs;});
		v.resize(unique(v.begin(),v.end())-v.begin());
		for(auto &i:v)cerr<<i<<',';cerr<<endl;
		for(int i = 1;i<v.size();i++){
			int a = v[i],b = tr.LCA(v[i],v[i-1]);
			cerr<<a<<':'<<b<<endl;
			assert(a != b);
			re.add_edge(a,b);
			re.add_edge(b,a);
		}
		re.dfs(rt1,rt1);
		return re;
	}
}

vector<pii> req;
vector<ai4> res;
vector<pii> ans;
int C = 0;
void ask(int a,int b){
	C++;
	assert(C<=K*2-2);
	cout<<"? "<<a<<' '<<b<<'\n';
	req.push_back(pii(a,b));
	res.push_back(ai4({0,0,0,0}));
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin.exceptions(cin.failbit);
	cin>>N>>K>>Q>>T;
	t1.init(N+1);t2.init(N+1);
	for(int i = 1;i<=N;i++){
		int p;
		cin>>p;
		if(p == -1)rt1 = i;
		else{
			t1.add_edge(p,i);
			t1.add_edge(i,p);
		}
	}
	for(int i = 1;i<=N;i++){
		int p;
		cin>>p;
		if(p == -1)rt2 = i;
		else{
			t2.add_edge(p,i);
			t2.add_edge(i,p);
		}
	}
	t1.dfs(rt1,rt1);t2.dfs(rt1,rt1);
	for(int i = 0;i<K;i++)tar.push_back(t1.dfn[i]);
	for(auto &i:tar)cout<<i<<' ';cout<<endl;
	vt = PEKO::GO(tar,t2);
	for(int i = 1;i<=N;i++){
		if(!vt.edges[i].empty()&&i != rt1){
			ask(rt1,i);
		}
	}
	cout<<"!"<<endl;
	for(int i = 0;i<req.size();i++){
		auto [a,b] = req[i];
		for(auto &j:res[i])cin>>j;
		val1[b] = res[i][1];
		val2[b] = res[i][2]+res[i][3];
	}
	while(T--){
		int a,b;
		cin>>a>>b;
		pii tans;
		assert(vt.LCA(a,b)<=N);
		tans.fs = 1ll*val1[a]+val1[b]-val1[t1.LCA(a,b)]*2;
		tans.sc = 1ll*val2[a]+val2[b]-val2[vt.LCA(a,b)]*2;
		ans.push_back(tans);
	}
	for(auto &i:ans)cout<<i.fs<<' '<<i.sc<<'\n';
	cout<<endl;
	return 0;
}

Compilation message

Main.cpp: In function 'Tree PEKO::GO(std::vector<int>, Tree&)':
Main.cpp:77:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   77 |   for(auto &i:v)cerr<<i<<',';cerr<<endl;
      |   ^~~
Main.cpp:77:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |   for(auto &i:v)cerr<<i<<',';cerr<<endl;
      |                              ^~~~
Main.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i = 1;i<v.size();i++){
      |                 ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:128:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  128 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |  ^~~
Main.cpp:128:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  128 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |                               ^~~~
Main.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2153 ms 378300 KB Output is correct
2 Correct 2393 ms 381760 KB Output is correct
3 Correct 1521 ms 357120 KB Output is correct
4 Correct 1460 ms 356160 KB Output is correct
5 Correct 1858 ms 359220 KB Output is correct
6 Correct 2061 ms 361288 KB Output is correct
7 Correct 1832 ms 361204 KB Output is correct
8 Correct 1920 ms 361016 KB Output is correct
9 Correct 1488 ms 356968 KB Output is correct
10 Correct 1600 ms 358408 KB Output is correct
11 Correct 1329 ms 354536 KB Output is correct
12 Correct 1473 ms 357984 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2408 ms 381828 KB Output is correct
2 Correct 2033 ms 376372 KB Output is correct
3 Runtime error 1427 ms 351620 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 366788 KB Output is correct
2 Correct 1422 ms 366680 KB Output is correct
3 Runtime error 978 ms 693580 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3510 ms 735460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3617 ms 579896 KB Time limit exceeded
2 Halted 0 ms 0 KB -