oj.uz

답안 #1035060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035060 2024-07-26T03:38:40 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 767128 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;

namespace PEKO{
	Tree re;
	Tree GO(vector<int> v,Tree& tr){
		re.init(N+1);
		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(auto &i:v)cerr<<i<<',';cerr<<endl;
		for(int i = 1;i<v.size();i++){
			int a = v[i],b = tr.LCA(v[i],v[i-1]);
			//cerr<<a<<':'<<b<<endl;
			assert(a != b);
			re.add_edge(a,b);
			re.add_edge(b,a);
		}
		re.dfs(rt1,rt1);
		return re;
	}
}

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1494 ms 219912 KB Output is correct
2 Correct 1750 ms 221316 KB Output is correct
3 Correct 934 ms 198496 KB Output is correct
4 Correct 892 ms 197432 KB Output is correct
5 Correct 904 ms 199020 KB Output is correct
6 Correct 1166 ms 201804 KB Output is correct
7 Correct 1276 ms 202796 KB Output is correct
8 Correct 1156 ms 202172 KB Output is correct
9 Correct 921 ms 198184 KB Output is correct
10 Correct 1048 ms 198588 KB Output is correct
11 Correct 867 ms 197196 KB Output is correct
12 Correct 927 ms 198820 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1772 ms 221160 KB Output is correct
2 Correct 1655 ms 219460 KB Output is correct
3 Runtime error 756 ms 190892 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1641 ms 213932 KB Output is correct
2 Correct 1391 ms 214032 KB Output is correct
3 Runtime error 802 ms 383904 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3308 ms 430060 KB Output is correct
2 Correct 3303 ms 430172 KB Output is correct
3 Runtime error 1799 ms 767128 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3532 ms 436264 KB Time limit exceeded
2 Halted 0 ms 0 KB -