| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 633031 |
2022-08-21T12:17:18 Z |
DJeniUp |
Prize (CEOI22_prize) |
C++17 |
|
2258 ms |
515296 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;
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)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)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){
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)v1[p1[i][0]].pb(i);
if(p2[i][0]!=-1)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);
vector<pair<int,int> >ans;
ans.clear();
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)});
}
for(int i=0;i<t;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:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'void CH2(ll)':
Main.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<vf[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void BT1(ll, ll)':
Main.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'void BT2(ll, ll)':
Main.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<vf[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void T1(ll)':
Main.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=0;i<v1[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void T2(ll)':
Main.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void S(ll, ll)':
Main.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:187:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D2(ll, ll)':
Main.cpp:196:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D1(ll, ll)':
Main.cpp:205: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]
205 | for(int i=0;i<l[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1234 ms |
318984 KB |
Output is correct |
| 2 |
Correct |
1390 ms |
321588 KB |
Output is correct |
| 3 |
Correct |
952 ms |
263444 KB |
Output is correct |
| 4 |
Correct |
976 ms |
263120 KB |
Output is correct |
| 5 |
Correct |
1110 ms |
265016 KB |
Output is correct |
| 6 |
Correct |
1146 ms |
276260 KB |
Output is correct |
| 7 |
Correct |
1098 ms |
276184 KB |
Output is correct |
| 8 |
Correct |
1075 ms |
275700 KB |
Output is correct |
| 9 |
Correct |
885 ms |
263528 KB |
Output is correct |
| 10 |
Correct |
941 ms |
264440 KB |
Output is correct |
| 11 |
Correct |
822 ms |
262496 KB |
Output is correct |
| 12 |
Correct |
941 ms |
264344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1223 ms |
321452 KB |
Output is correct |
| 2 |
Correct |
1116 ms |
317660 KB |
Output is correct |
| 3 |
Runtime error |
712 ms |
254516 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
877 ms |
301892 KB |
Output is correct |
| 2 |
Correct |
894 ms |
301828 KB |
Output is correct |
| 3 |
Runtime error |
583 ms |
249276 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1882 ms |
495020 KB |
Output is correct |
| 2 |
Correct |
2013 ms |
495452 KB |
Output is correct |
| 3 |
Runtime error |
1298 ms |
391448 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2258 ms |
515296 KB |
Output is correct |
| 2 |
Correct |
2221 ms |
514680 KB |
Output is correct |
| 3 |
Runtime error |
1347 ms |
387872 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
