Submission #633040

# Submission time Handle Problem Language Result Execution time Memory
633040 2022-08-21T12:41:11 Z DJeniUp Prize (CEOI22_prize) C++17
10 / 100
2185 ms 515176 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 || 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);
 
    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 1079 ms 319112 KB Output is correct
2 Correct 1169 ms 321612 KB Output is correct
3 Correct 942 ms 263552 KB Output is correct
4 Correct 831 ms 263292 KB Output is correct
5 Correct 902 ms 265020 KB Output is correct
6 Correct 1061 ms 276276 KB Output is correct
7 Correct 1085 ms 276256 KB Output is correct
8 Correct 1057 ms 275836 KB Output is correct
9 Correct 897 ms 263448 KB Output is correct
10 Correct 879 ms 264472 KB Output is correct
11 Correct 821 ms 262444 KB Output is correct
12 Correct 871 ms 264148 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1269 ms 321508 KB Output is correct
2 Correct 1119 ms 317584 KB Output is correct
3 Runtime error 814 ms 258464 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 870 ms 301880 KB Output is correct
2 Correct 872 ms 301844 KB Output is correct
3 Runtime error 574 ms 249316 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1846 ms 494944 KB Output is correct
2 Correct 1843 ms 495456 KB Output is correct
3 Runtime error 1218 ms 391452 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2151 ms 515176 KB Output is correct
2 Correct 2185 ms 514788 KB Output is correct
3 Runtime error 1245 ms 387984 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -