| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 631909 |
2022-08-19T06:28:29 Z |
DJeniUp |
Prize (CEOI22_prize) |
C++17 |
|
3110 ms |
1048576 KB |
#pragma GCC Optimize("O3")
#include "bits/stdc++.h"
using namespace std;
typedef long long 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];
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=20;i>=0;i--){
if(tout1[p1[g][i]]<tout1[y])g=p1[g][i];
}
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=20;i>=0;i--){
if(tout2[p2[g][i]]<tout2[y])g=p2[g][i];
}
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){
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!=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!=m1){
l[m1].pb({par,-A});
l[par].pb({m1,A});
}
if(par!=m2){
l[m2].pb({par,-B});
l[par].pb({m2,B});
}
}
}
}
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;
flag[x]=1;
for(int i=0;i<v2[x].size();i++){
D2(v2[x][i],y);
}
return ;
}
void D1(ll x,ll y){
t1[x]=y;
for(int i=0;i<l[x].size();i++){
if(t1[l[x][i].fr]==0 && l[x][i].fr!=par1){
D1(l[x][i].fr,y+l[x][i].sc);
}
}
return ;
}
int main()
{
cin>>n>>k>>q>>t;
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;
}
}
p1[par1][0]=0;
tout1[0]=INF;
p2[par2][0]=0;
tout2[0]=INF;
for(int i=1;i<=20;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);
cout<<"!"<<endl;
cout.flush();
S(par2,1);
D2(par2,0);
D1(par1,0);
vector<pair<int,int> >ans;
ans.clear();
/*for(int i=1;i<=n;i++){
if(f[i]==1 && flag[i]!=1)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);
//exit(1);
//if(pr1<1 || pr1>n || pr2<1 || pr2>n || x<1 || x>n || y<1 || y>n)exit(1);
//exit(1);
ans.push_back({(t1[x]+t1[y]-t1[pr1]*2),(t2[x]+t2[y]-t2[pr2]*2)});
//cout<<1<<" "<<1<<endl;
//exit(1);
}
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<long long 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<long long 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<long long 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<long long 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<long long 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<long long 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:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:178:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D2(ll, ll)':
Main.cpp:188:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D1(ll, ll)':
Main.cpp:196:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int i=0;i<l[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1520 ms |
443624 KB |
Output is correct |
| 2 |
Correct |
1709 ms |
446940 KB |
Output is correct |
| 3 |
Correct |
1249 ms |
391228 KB |
Output is correct |
| 4 |
Correct |
1285 ms |
390332 KB |
Output is correct |
| 5 |
Correct |
1348 ms |
393104 KB |
Output is correct |
| 6 |
Correct |
1544 ms |
402636 KB |
Output is correct |
| 7 |
Correct |
1649 ms |
402580 KB |
Output is correct |
| 8 |
Correct |
1517 ms |
401844 KB |
Output is correct |
| 9 |
Correct |
1279 ms |
391020 KB |
Output is correct |
| 10 |
Correct |
1295 ms |
392612 KB |
Output is correct |
| 11 |
Correct |
1195 ms |
389592 KB |
Output is correct |
| 12 |
Correct |
1408 ms |
392084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1612 ms |
446760 KB |
Output is correct |
| 2 |
Correct |
1428 ms |
441768 KB |
Output is correct |
| 3 |
Runtime error |
1020 ms |
375208 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1184 ms |
410140 KB |
Output is correct |
| 2 |
Correct |
1153 ms |
409924 KB |
Output is correct |
| 3 |
Runtime error |
1183 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2400 ms |
715332 KB |
Output is correct |
| 2 |
Correct |
2404 ms |
715796 KB |
Output is correct |
| 3 |
Runtime error |
1977 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2991 ms |
763932 KB |
Output is correct |
| 2 |
Correct |
3110 ms |
763336 KB |
Output is correct |
| 3 |
Runtime error |
1868 ms |
628480 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
