| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 631906 |
2022-08-19T06:17:45 Z |
DJeniUp |
Prize (CEOI22_prize) |
C++17 |
|
2903 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef unsigned long long ull;
typedef long double ld;
#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){
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){
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: In function 'void CH(ll)':
Main.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'void CH2(ll)':
Main.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<vf[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void BT1(ll, ll)':
Main.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'void BT2(ll, ll)':
Main.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0;i<vf[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void T1(ll)':
Main.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i=0;i<v1[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void T2(ll)':
Main.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void S(ll, ll)':
Main.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:170:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D2(ll, ll)':
Main.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i=0;i<v2[x].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void D1(ll, ll)':
Main.cpp:188: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]
188 | for(int i=0;i<l[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1520 ms |
319080 KB |
Output is correct |
| 2 |
Correct |
1613 ms |
321516 KB |
Output is correct |
| 3 |
Correct |
1151 ms |
263452 KB |
Output is correct |
| 4 |
Correct |
1172 ms |
263156 KB |
Output is correct |
| 5 |
Correct |
1195 ms |
264944 KB |
Output is correct |
| 6 |
Correct |
1402 ms |
276220 KB |
Output is correct |
| 7 |
Correct |
1447 ms |
276236 KB |
Output is correct |
| 8 |
Correct |
1371 ms |
275640 KB |
Output is correct |
| 9 |
Correct |
1204 ms |
263396 KB |
Output is correct |
| 10 |
Correct |
1320 ms |
264452 KB |
Output is correct |
| 11 |
Correct |
1101 ms |
262512 KB |
Output is correct |
| 12 |
Correct |
1233 ms |
264252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1536 ms |
321324 KB |
Output is correct |
| 2 |
Correct |
1510 ms |
317724 KB |
Output is correct |
| 3 |
Runtime error |
956 ms |
254412 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1103 ms |
301760 KB |
Output is correct |
| 2 |
Correct |
1142 ms |
301928 KB |
Output is correct |
| 3 |
Runtime error |
1249 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2395 ms |
494920 KB |
Output is correct |
| 2 |
Correct |
2381 ms |
495456 KB |
Output is correct |
| 3 |
Runtime error |
1924 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2790 ms |
515324 KB |
Output is correct |
| 2 |
Correct |
2903 ms |
514608 KB |
Output is correct |
| 3 |
Runtime error |
1772 ms |
387940 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
