oj.uz

Submission #1035027

# Submission time Handle Problem Language Result Execution time Memory
1035027 2024-07-26T03:13:50 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 1009220 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 GO(vector<int> v,Tree& tr){
		cerr<<"PEKOPEKOPEKOPEKOPEKO!"<<endl;
		Tree re;
		re.init(tr.edges.size());
		cerr<<"PEKOPEKOPEKOPEKO!"<<endl;
		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]));
		}
		cerr<<"PEKOPEKOPEKO!"<<endl;
		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);
		cerr<<"PEKOPEKO!"<<endl;
		return re;
	}
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1533 ms 305012 KB Output is correct
2 Correct 1618 ms 307584 KB Output is correct
3 Correct 1006 ms 267068 KB Output is correct
4 Correct 875 ms 266420 KB Output is correct
5 Correct 960 ms 268748 KB Output is correct
6 Correct 1185 ms 276504 KB Output is correct
7 Correct 1259 ms 276164 KB Output is correct
8 Correct 1185 ms 276220 KB Output is correct
9 Correct 878 ms 266924 KB Output is correct
10 Correct 1065 ms 268140 KB Output is correct
11 Correct 972 ms 267112 KB Output is correct
12 Correct 1042 ms 267816 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2098 ms 307664 KB Output is correct
2 Correct 1585 ms 304020 KB Output is correct
3 Runtime error 787 ms 254248 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 1267 ms 291244 KB Output is correct
2 Correct 1225 ms 291468 KB Output is correct
3 Runtime error 763 ms 505788 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 2928 ms 585968 KB Output is correct
2 Correct 3221 ms 585960 KB Output is correct
3 Runtime error 1720 ms 1009220 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 3547 ms 602480 KB Time limit exceeded
2 Halted 0 ms 0 KB -