제출 #632982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632982		DJeniUp	Prize (CEOI22_prize)	C++17	10 / 100	2143 ms	515296 KiB

Main

#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];
 
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(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=16;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++){
        if(q1>0)w.push(v2[x][i]);
    }
    while(w.size()>0 && q1>0){
        if(w.size()==1){
            q1--;
            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{
            q1--;
            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;
    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);
 
    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
 
*/

컴파일 시 표준 에러 (stderr) 메시지

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:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=0;i<v2[x].size();i++){
      |                 ~^~~~~~~~~~~~~
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 D2(ll, ll)':
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 D1(ll, ll)':
Main.cpp:198: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]
  198 |     for(int i=0;i<l[x].size();i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24