oj.uz

Submission #1034984

# Submission time Handle Problem Language Result Execution time Memory
1034984 2024-07-26T02:08:16 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 2990 ms 438244 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#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;
int rt1,rt2;
int N,K,Q,T;
ll val1[mxn],val2[mxn];
vector<int> tar;

vector<pii> req;
vector<al4> res;
void ask(int a,int b){
	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;
	for(int i = 1;i<K;i++){
		ask(tar[0],tar[i]);
	}
	cout<<"!"<<endl;
	for(int i = 0;i<req.size();i++){
		for(auto &j:res[i])cin>>j;
		val1[req[i].sc] = res[i][1];
	}
	vector<ll> ans;
	while(T--){
		int a,b;
		cin>>a>>b;
		ll tans = val1[a]+val1[b]-val1[t1.LCA(a,b)]*2;
		ans.push_back(tans);
	}
	for(auto &i:ans)cout<<i<<' '<<i<<'\n';
	cout<<endl;
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:89:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   89 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |  ^~~
Main.cpp:89:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   89 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |                               ^~~~
Main.cpp:94: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]
   94 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 220420 KB Output is correct
2 Correct 1360 ms 222044 KB Output is correct
3 Correct 696 ms 182500 KB Output is correct
4 Correct 736 ms 182384 KB Output is correct
5 Correct 734 ms 183316 KB Output is correct
6 Correct 988 ms 191548 KB Output is correct
7 Correct 954 ms 191476 KB Output is correct
8 Correct 960 ms 191144 KB Output is correct
9 Correct 721 ms 182556 KB Output is correct
10 Correct 722 ms 183364 KB Output is correct
11 Correct 707 ms 181428 KB Output is correct
12 Correct 715 ms 183020 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1313 ms 221724 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1188 ms 213420 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2813 ms 428136 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2990 ms 438244 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -