oj.uz

Submission #1035030

# Submission time Handle Problem Language Result Execution time Memory
1035030 2024-07-26T03:16:14 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 1048576 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>

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;
	void init(int n){
		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;
ll val1[mxn],val2[mxn];
vector<int> tar;

namespace PEKO{
	Tree re;
	Tree GO(vector<int> v,Tree& tr){
		re.init(tr.edges.size());
		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(int i = 1;i<v.size();i++){
			int a = v[i],b = tr.LCA(v[i],v[i-1]);
			re.add_edge(a,b);
			re.add_edge(b,a);
		}
		re.dfs(rt1,rt1);
		return re;
	}
}

vector<pii> req;
vector<al4> res;
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(al4({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);
	}
	for(int i = 1;i<=N;i++){
		int p;
		cin>>p;
		if(p == -1)rt2 = i;
		else t2.add_edge(p,i);
	}
	t1.dfs(rt1,rt1);t2.dfs(rt2,rt2);
	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];
	}
	vector<pll> ans;
	while(T--){
		int a,b;
		cin>>a>>b;
		pll tans;
		tans.fs = val1[a]+val1[b]-val1[t1.LCA(a,b)]*2;
		tans.sc = 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:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i = 1;i<v.size();i++){
      |                 ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:114:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  114 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |  ^~~
Main.cpp:114:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  114 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |                               ^~~~
Main.cpp:122: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]
  122 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 383600 KB Output is correct
2 Correct 1686 ms 387256 KB Output is correct
3 Correct 938 ms 346064 KB Output is correct
4 Correct 923 ms 345024 KB Output is correct
5 Correct 1038 ms 348072 KB Output is correct
6 Correct 1280 ms 355532 KB Output is correct
7 Correct 1181 ms 355272 KB Output is correct
8 Correct 1281 ms 354988 KB Output is correct
9 Correct 911 ms 345524 KB Output is correct
10 Correct 1033 ms 347388 KB Output is correct
11 Correct 998 ms 343780 KB Output is correct
12 Correct 956 ms 347220 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1731 ms 386776 KB Output is correct
2 Correct 1570 ms 382296 KB Output is correct
3 Runtime error 830 ms 333456 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 1422 ms 367664 KB Output is correct
2 Correct 1338 ms 367592 KB Output is correct
3 Runtime error 864 ms 660644 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3085 ms 738504 KB Output is correct
2 Correct 3203 ms 738652 KB Output is correct
3 Execution timed out 4105 ms 1048576 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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