oj.uz

Submission #1035073

# Submission time Handle Problem Language Result Execution time Memory
1035073 2024-07-26T03:48:48 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 767268 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);
		}
	}
	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:117: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]
  117 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 220048 KB Output is correct
2 Correct 1590 ms 221236 KB Output is correct
3 Correct 838 ms 198668 KB Output is correct
4 Correct 852 ms 197524 KB Output is correct
5 Correct 928 ms 198792 KB Output is correct
6 Correct 1216 ms 201804 KB Output is correct
7 Correct 1095 ms 202096 KB Output is correct
8 Correct 1135 ms 201588 KB Output is correct
9 Correct 820 ms 198024 KB Output is correct
10 Correct 882 ms 198764 KB Output is correct
11 Correct 774 ms 197196 KB Output is correct
12 Correct 828 ms 198452 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 221284 KB Output is correct
2 Correct 1546 ms 219464 KB Output is correct
3 Runtime error 684 ms 191028 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 1205 ms 213964 KB Output is correct
2 Correct 1351 ms 214008 KB Output is correct
3 Runtime error 736 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 3204 ms 430132 KB Output is correct
2 Correct 3174 ms 430184 KB Output is correct
3 Runtime error 1730 ms 767268 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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