답안 #633026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633026 2022-08-21T12:13:24 Z DJeniUp Prize (CEOI22_prize) C++17
10 / 100
2484 ms 515184 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 && 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!=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);
    
    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: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++){
      |                 ~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1202 ms 319060 KB Output is correct
2 Correct 1424 ms 321512 KB Output is correct
3 Correct 1053 ms 263544 KB Output is correct
4 Correct 1051 ms 263188 KB Output is correct
5 Correct 1061 ms 264936 KB Output is correct
6 Correct 1215 ms 276220 KB Output is correct
7 Correct 1332 ms 276228 KB Output is correct
8 Correct 1337 ms 275624 KB Output is correct
9 Correct 1014 ms 263360 KB Output is correct
10 Correct 1054 ms 264476 KB Output is correct
11 Correct 931 ms 262556 KB Output is correct
12 Correct 1031 ms 264216 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1404 ms 321300 KB Output is correct
2 Correct 1165 ms 317548 KB Output is correct
3 Runtime error 816 ms 257208 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 985 ms 301892 KB Output is correct
2 Correct 1034 ms 301752 KB Output is correct
3 Runtime error 721 ms 249180 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1989 ms 494872 KB Output is correct
2 Correct 1947 ms 495408 KB Output is correct
3 Runtime error 1513 ms 391452 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2484 ms 515184 KB Output is correct
2 Correct 2404 ms 514784 KB Output is correct
3 Runtime error 1344 ms 387804 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -