oj.uz

답안 #631907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631907 2022-08-19T06:25:44 Z DJeniUp Prize (CEOI22_prize) C++17
10 / 100
 3181 ms 1048576 KB 
#pragma GCC Optimize("O3")
#include "bits/stdc++.h"

using namespace std;

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1588 ms 443688 KB Output is correct
2 Correct 1638 ms 446956 KB Output is correct
3 Correct 1268 ms 391168 KB Output is correct
4 Correct 1216 ms 390476 KB Output is correct
5 Correct 1288 ms 393056 KB Output is correct
6 Correct 1613 ms 402636 KB Output is correct
7 Correct 1742 ms 402656 KB Output is correct
8 Correct 1693 ms 401920 KB Output is correct
9 Correct 1411 ms 390996 KB Output is correct
10 Correct 1453 ms 392536 KB Output is correct
11 Correct 1289 ms 389364 KB Output is correct
12 Correct 1381 ms 392064 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1718 ms 446752 KB Output is correct
2 Correct 1480 ms 441788 KB Output is correct
3 Runtime error 1049 ms 375196 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1185 ms 409952 KB Output is correct
2 Correct 1219 ms 409924 KB Output is correct
3 Runtime error 1153 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2502 ms 715232 KB Output is correct
2 Correct 2502 ms 715716 KB Output is correct
3 Runtime error 1904 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3181 ms 763956 KB Output is correct
2 Correct 2955 ms 763320 KB Output is correct
3 Runtime error 2017 ms 628516 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -