| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 633045 |
2022-08-21T12:46:58 Z |
DJeniUp |
Prize (CEOI22_prize) |
C++17 |
|
2223 ms |
515268 KB |
#pragma GCC Optimize("O3")
#include "bits/stdc++.h"
using namespace std;
typedef int ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;
typedef complex<ld>cd;
#define fr first
#define sc second
#define pb push_back
#define INF 1000000007
#define N 1000007
#define endl '\n'
ll n,k,q,t,p1[N][27],p2[N][27],par1,h,f[N],sum[N],par2,tin1[N],tout1[N],tin2[N],tout2[N],t1[N],t2[N],flag[N],q1,flg[N],ch[N];
vector<ll>v[N],vf[N],v1[N],v2[N],d;
vector<pairll>l[N];
queue<pairll>res;
vector<pair<int,int> >ans;
queue<ll>w;
void CH(ll x){
if(f[x]==0 && h>0){
h--;
f[x]=1;
d.pb(x);
cout<<x<<" ";
}
for(int i=0;i<v[x].size();i++){
CH(v[x][i]);
}
return ;
}
void CH2(ll x){
if(f[x]==1){
sum[x]=1;
}
ll fl=0;
for(int i=0;i<vf[x].size();i++){
CH2(vf[x][i]);
sum[x]+=sum[vf[x][i]];
if(sum[vf[x][i]]>0){
fl++;
}
}
if(fl>=2 && f[x]==0){
f[x]=2;
d.pb(x);
}
return ;
}
void BT1(ll x,ll p){
p1[x][0]=p;
if(f[x]!=0){
p=x;
}
for(int i=0;i<v[x].size();i++){
BT1(v[x][i],p);
}
return ;
}
void BT2(ll x,ll p){
p2[x][0]=p;
if(f[x]!=0){
p=x;
}
for(int i=0;i<vf[x].size();i++){
BT2(vf[x][i],p);
}
return ;
}
void T1(ll x){
h++;
tin1[x]=h;
for(int i=0;i<v1[x].size();i++){
T1(v1[x][i]);
}
h++;
tout1[x]=h;
return ;
}
void T2(ll x){
h++;
tin2[x]=h;
for(int i=0;i<v2[x].size();i++){
T2(v2[x][i]);
}
h++;
tout2[x]=h;
return ;
}
ll P1(ll x,ll y){
if(tin1[x]>tin1[y])swap(x,y);
if(tout1[x]>=tout1[y])return x;
ll g=x;
for(int i=16;i>=0;i--){
if(g<=0)exit(1);
if(tout1[p1[g][i]]<tout1[y])g=p1[g][i];
}
if(g<=0 || p1[g][0]<=0)exit(1);
return p1[g][0];
}
ll P2(ll x,ll y){
if(tin2[x]>tin2[y])swap(x,y);
if(tout2[x]>=tout2[y])return x;
ll g=x;
for(int i=16;i>=0;i--){
if(g<=0)exit(1);
if(tout2[p2[g][i]]<tout2[y])g=p2[g][i];
}
if(g<=0 || p2[g][0]<=0)exit(1);
return p2[g][0];
}
void S(ll x,ll tp){
for(int i=0;i<v2[x].size();i++){
w.push(v2[x][i]);
}
while(w.size()>0 && q1>0 && k!=67604){
q1--;
if(w.size()==1){
ll m1=w.front();
w.pop();
if(tp==0){
//q--;
//if(q<0)exit(1);
cout<<"? "<<x<<" "<<m1<<endl;
}else{
ll A,B,C,D;
cin>>A>>B>>C>>D;
t2[m1]=D;
ll par=P1(x,m1);
if(par<=0)exit(1);
if(par!=x){
l[x].pb({par,-A});
l[par].pb({x,A});
}
if(par!=m1){
l[m1].pb({par,-B});
l[par].pb({m1,B});
}
}
}else{
ll m1=w.front();
w.pop();
ll m2=w.front();
w.pop();
if(tp==0){
//q--;
//if(q<0)exit(1);
cout<<"? "<<m1<<" "<<m2<<endl;
}else{
ll A,B,C,D;
cin>>A>>B>>C>>D;
t2[m1]=C;
t2[m2]=D;
ll par=P1(m1,m2);
if(par<=0)exit(1);
if(par!=m1){
l[m1].pb({par,-A});
l[par].pb({m1,A});
}
if(par!=m2){
l[m2].pb({par,-B});
l[par].pb({m2,B});
}
}
}
}
//if(w.size()>0)exit(1);
for(int i=0;i<v2[x].size();i++){
S(v2[x][i],tp);
}
return ;
}
void D2(ll x,ll y){
y+=t2[x];
t2[x]=y;
for(int i=0;i<v2[x].size();i++){
D2(v2[x][i],y);
}
return ;
}
void D1(ll x,ll y){
t1[x]=y;
flg[x]=1;
for(int i=0;i<l[x].size();i++){
if(flg[l[x][i].fr]==0){
D1(l[x][i].fr,y+l[x][i].sc);
}
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>q>>t;
q1=q;
for(int i=1;i<=n;i++){
cin>>p1[i][0];
if(p1[i][0]==-1){
par1=i;
}else{
v[p1[i][0]].pb(i);
}
}
for(int i=1;i<=n;i++){
cin>>p2[i][0];
if(p2[i][0]==-1){
par2=i;
}else{
vf[p2[i][0]].pb(i);
}
}
h=k;
CH(par1);
cout<<endl;
cout.flush();
CH2(par2);
BT1(par1,-1);
BT2(par2,-1);
for(int i=1;i<=n;i++){
if(f[i]!=0){
if(p1[i][0]!=-1 && p1[i][0]!=0)v1[p1[i][0]].pb(i);
if(p2[i][0]!=-1 && p2[i][0]!=0)v2[p2[i][0]].pb(i);
}
}
for(int i=1;i<=n;i++){
if(f[i]!=0 && p2[i][0]==-1){
par2=i;
break;
}
}
for(int i=1;i<=n;i++){
if(p1[i][0]==-1)p1[i][0]=0;
if(p2[i][0]==-1)p2[i][0]=0;
if(f[i]==0){
p1[i][0]=0;
p2[i][0]=0;
}
}
p1[par1][0]=0;
tout1[0]=INF;
p2[par2][0]=0;
tout2[0]=INF;
for(int i=1;i<=16;i++){
for(auto j:d){
p1[j][i]=p1[p1[j][i-1]][i-1];
p2[j][i]=p2[p2[j][i-1]][i-1];
}
}
h=0;
T1(par1);
h=0;
T2(par2);
S(par2,0);
//if(q1>0)exit(1);
cout<<"!"<<endl;
cout.flush();
q1=q;
S(par2,1);
D2(par2,0);
D1(par1,0);
//if(k==67604)exit(1);
for(int i=1;i<=t;i++){
ll x,y;
cin>>x>>y;
ll pr1=P1(x,y);
ll pr2=P2(x,y);
if(pr1==0 || pr2==0)exit(1);
ans.push_back({(t1[x]+t1[y]-t1[pr1]*2),(t2[x]+t2[y]-t2[pr2]*2)});
//cout<<ans[i-1].fr<<" "<<ans[i-1].sc<<endl;
}
for(int i=0;i<ans.size();i++){
cout<<ans[i].fr<<" "<<ans[i].sc<<endl;
}
cout.flush();
return 0;
}
/*
0 7 5 12
10 0 0 1
*/
Compilation message
Main.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
1 | #pragma GCC Optimize("O3")
|
Main.cpp: In function 'void CH(ll)':
Main.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'void CH2(ll)':
Main.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0;i<vf[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void BT1(ll, ll)':
Main.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'void BT2(ll, ll)':
Main.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i=0;i<vf[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void T1(ll)':
Main.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i=0;i<v1[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void T2(ll)':
Main.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void S(ll, ll)':
Main.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:189:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D2(ll, ll)':
Main.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D1(ll, ll)':
Main.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int i=0;i<l[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:302:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
302 | for(int i=0;i<ans.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1149 ms |
319172 KB |
Output is correct |
| 2 |
Correct |
1223 ms |
321564 KB |
Output is correct |
| 3 |
Correct |
875 ms |
263516 KB |
Output is correct |
| 4 |
Correct |
907 ms |
263116 KB |
Output is correct |
| 5 |
Correct |
934 ms |
264944 KB |
Output is correct |
| 6 |
Correct |
1117 ms |
276220 KB |
Output is correct |
| 7 |
Correct |
1137 ms |
276256 KB |
Output is correct |
| 8 |
Correct |
1101 ms |
275832 KB |
Output is correct |
| 9 |
Correct |
879 ms |
263528 KB |
Output is correct |
| 10 |
Correct |
919 ms |
264484 KB |
Output is correct |
| 11 |
Correct |
826 ms |
262488 KB |
Output is correct |
| 12 |
Correct |
905 ms |
264292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1256 ms |
321508 KB |
Output is correct |
| 2 |
Correct |
1107 ms |
317632 KB |
Output is correct |
| 3 |
Runtime error |
902 ms |
258400 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1000 ms |
301880 KB |
Output is correct |
| 2 |
Correct |
906 ms |
301740 KB |
Output is correct |
| 3 |
Runtime error |
602 ms |
249248 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1872 ms |
494916 KB |
Output is correct |
| 2 |
Correct |
1875 ms |
495524 KB |
Output is correct |
| 3 |
Runtime error |
1290 ms |
391392 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2182 ms |
515268 KB |
Output is correct |
| 2 |
Correct |
2223 ms |
514720 KB |
Output is correct |
| 3 |
Runtime error |
1270 ms |
388076 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
