oj.uz

답안 #631906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631906 2022-08-19T06:17:45 Z DJeniUp Prize (CEOI22_prize) C++17
10 / 100
 2903 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef unsigned long long ull;
typedef long double ld;

#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: In function 'void CH(ll)':
Main.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
Main.cpp: In function 'void CH2(ll)':
Main.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<vf[x].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function 'void BT1(ll, ll)':
Main.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
Main.cpp: In function 'void BT2(ll, ll)':
Main.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<vf[x].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function 'void T1(ll)':
Main.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<v1[x].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function 'void T2(ll)':
Main.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=0;i<v2[x].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function 'void S(ll, ll)':
Main.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<v2[x].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:170:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for(int i=0;i<v2[x].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function 'void D2(ll, ll)':
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 D1(ll, ll)':
Main.cpp:188: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]
  188 |     for(int i=0;i<l[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1520 ms 319080 KB Output is correct
2 Correct 1613 ms 321516 KB Output is correct
3 Correct 1151 ms 263452 KB Output is correct
4 Correct 1172 ms 263156 KB Output is correct
5 Correct 1195 ms 264944 KB Output is correct
6 Correct 1402 ms 276220 KB Output is correct
7 Correct 1447 ms 276236 KB Output is correct
8 Correct 1371 ms 275640 KB Output is correct
9 Correct 1204 ms 263396 KB Output is correct
10 Correct 1320 ms 264452 KB Output is correct
11 Correct 1101 ms 262512 KB Output is correct
12 Correct 1233 ms 264252 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1536 ms 321324 KB Output is correct
2 Correct 1510 ms 317724 KB Output is correct
3 Runtime error 956 ms 254412 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1103 ms 301760 KB Output is correct
2 Correct 1142 ms 301928 KB Output is correct
3 Runtime error 1249 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2395 ms 494920 KB Output is correct
2 Correct 2381 ms 495456 KB Output is correct
3 Runtime error 1924 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2790 ms 515324 KB Output is correct
2 Correct 2903 ms 514608 KB Output is correct
3 Runtime error 1772 ms 387940 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -