oj.uz

Submission #1035079

# Submission time Handle Problem Language Result Execution time Memory
1035079 2024-07-26T03:55:30 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 441648 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;
int rt1,rt2;
int N,K,Q,T;
int val1[mxn],val2[mxn];
vector<int> tar;

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;
	int s = tar.size();
	sort(tar.begin(),tar.end(),[&](int a,int b){return t2.eul[a].fs<t2.eul[b].fs;});
	for(int i = 1;i<s;i++)tar.push_back(t2.LCA(tar[i],tar[i-1]));
	sort(tar.begin(),tar.end(),[&](int a,int b){return t2.eul[a].fs<t2.eul[b].fs;});
	tar.resize(unique(tar.begin(),tar.end())-tar.begin());
	assert(tar.size()<=K*2-1);
	for(auto &i:tar){
		if(i != rt1){
			ask(rt1,i);
		}
	}
	while(req.size() < K*2-2){
		ask(rt1,rt1);
	}
	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;
		if(a == b)ans.push_back(pll(0,0));
		else{
			pii tans;
			tans.fs = 1ll*val1[a]+val1[b]-val1[t1.LCA(a,b)]*2;
			tans.sc = 1ll*val2[a]+val2[b]-val2[t2.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 'int main()':
Main.cpp:104:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  104 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |  ^~~
Main.cpp:104:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  104 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |                               ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp:110:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  assert(tar.size()<=K*2-1);
      |         ~~~~~~~~~~^~~~~~~
Main.cpp:116:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |  while(req.size() < K*2-2){
      |        ~~~~~~~~~~~^~~~~~~
Main.cpp:120: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]
  120 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1640 ms 222176 KB Output is correct
2 Correct 1684 ms 223372 KB Output is correct
3 Correct 905 ms 199500 KB Output is correct
4 Correct 891 ms 200020 KB Output is correct
5 Correct 911 ms 200572 KB Output is correct
6 Correct 1193 ms 203652 KB Output is correct
7 Correct 1171 ms 203776 KB Output is correct
8 Correct 1248 ms 203012 KB Output is correct
9 Correct 901 ms 199412 KB Output is correct
10 Correct 904 ms 200244 KB Output is correct
11 Correct 934 ms 199352 KB Output is correct
12 Correct 1060 ms 200044 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2129 ms 223512 KB Output is correct
2 Correct 1835 ms 222220 KB Output is correct
3 Runtime error 687 ms 191288 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 1282 ms 213928 KB Output is correct
2 Correct 1346 ms 214064 KB Output is correct
3 Runtime error 794 ms 383900 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 3430 ms 430264 KB Output is correct
2 Execution timed out 3516 ms 430208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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