oj.uz

답안 #1035088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035088 2024-07-26T04:07:57 Z pcc Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 637436 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>
#define int ll

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;
ll val1[mxn],val2[mxn];
vector<int> tar;

vector<pii> req;
vector<al4> 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(al4({0,0,0,0}));
	return;
}

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)]*2ll;
			tans.sc = 1ll*val2[a]+val2[b]-val2[t2.LCA(a,b)]*2ll;
			ans.push_back(tans);
		}
	}
	for(auto &i:ans)cout<<i.fs<<' '<<i.sc<<'\n';
	cout<<endl;
	return 0;
}
//sig 13 = WA

Compilation message

Main.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:105:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |  ^~~
Main.cpp:105:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |  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:111:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  111 |  assert(tar.size()<=K*2-1);
      |         ~~~~~~~~~~^~~~~~~
Main.cpp:118:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1774 ms 321868 KB Output is correct
2 Correct 1792 ms 324500 KB Output is correct
3 Correct 1002 ms 305708 KB Output is correct
4 Correct 1043 ms 304588 KB Output is correct
5 Correct 987 ms 306916 KB Output is correct
6 Correct 1452 ms 309524 KB Output is correct
7 Correct 1321 ms 309292 KB Output is correct
8 Correct 1304 ms 308864 KB Output is correct
9 Correct 970 ms 305580 KB Output is correct
10 Correct 998 ms 306780 KB Output is correct
11 Correct 965 ms 303816 KB Output is correct
12 Correct 973 ms 306308 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1817 ms 324356 KB Output is correct
2 Correct 1853 ms 320956 KB Output is correct
3 Runtime error 737 ms 291352 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1459 ms 308792 KB Output is correct
2 Correct 1468 ms 308864 KB Output is correct
3 Runtime error 914 ms 584612 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3463 ms 621052 KB Output is correct
2 Execution timed out 3546 ms 621016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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