oj.uz

답안 #633018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633018 2022-08-21T12:07:51 Z DJeniUp Prize (CEOI22_prize) C++17
10 / 100
 2285 ms 515264 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(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++){
        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!=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});
                }
            }
        }
    }
    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);
    //if(k==67604)exit(1);
    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
 
*/

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1201 ms 318964 KB Output is correct
2 Correct 1262 ms 321588 KB Output is correct
3 Correct 871 ms 263500 KB Output is correct
4 Correct 904 ms 263284 KB Output is correct
5 Correct 954 ms 264956 KB Output is correct
6 Correct 1173 ms 276196 KB Output is correct
7 Correct 1187 ms 276240 KB Output is correct
8 Correct 1095 ms 275676 KB Output is correct
9 Correct 919 ms 263328 KB Output is correct
10 Correct 919 ms 264492 KB Output is correct
11 Correct 833 ms 262460 KB Output is correct
12 Correct 951 ms 264220 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1406 ms 321388 KB Output is correct
2 Correct 1121 ms 317604 KB Output is correct
3 Runtime error 753 ms 254584 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 940 ms 301888 KB Output is correct
2 Correct 869 ms 301748 KB Output is correct
3 Runtime error 604 ms 249160 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1872 ms 494928 KB Output is correct
2 Correct 1926 ms 495556 KB Output is correct
3 Runtime error 1301 ms 391492 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2218 ms 515264 KB Output is correct
2 Correct 2285 ms 514664 KB Output is correct
3 Runtime error 1339 ms 387952 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -