oj.uz

답안 #653122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653122 2022-10-25T18:54:03 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 2078 ms 524172 KB 
#include <bits/stdc++.h>

using namespace std;

//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=2000007;

vector<int>G1[N],G2[N];
vector<pair<int,int>>G3[N];
int d1[N],d2[N];
bool odw[N];
vector<pair<int,int>>X[N];
bool is[N];
int n,k,q,t;

int skok[N][20];
int pre[N];
int post[N];
int c=0;

void dfs(int v,int o)
{
    pre[v]=++c;
    skok[v][0]=o;
    for(int i=1;i<20;i++) skok[v][i]=skok[skok[v][i-1]][i-1];
    if(k>0)
    {
        cout<<v<<" ";
        is[v]=1;
        k--;
    }
    for(auto u:G1[v]) dfs(u,v);
    post[v]=++c;
}

int lca(int u,int v)
{
    if(pre[u]<=pre[v]&&post[u]>=post[v]) return u;
    if(pre[v]<=pre[u]&&post[v]>=post[u]) return v;
    for(int i=19;i>=0;i--) if(!(pre[skok[u][i]]<=pre[v]&&post[skok[u][i]]>=post[v])) u=skok[u][i];
    return skok[u][0];
}

vector<pair<pair<int,int>,int>>xd;

void qry(int u,int v,int x)
{
    cout<<"? "<<u<<" "<<v<<endl;
    xd.pb({{u,v},x});
  /*  */
}

int last[N];

void dfs1(int v)
{
    int l=0,c=0;
    for(auto u:G2[v])
    {
        dfs1(u);
        if(last[u]>0)
        {
            c++;
            if(is[v]) qry(last[u],v,v);
            else if(c>1) qry(l,last[u],v);
            else l=last[u];
        }
    }
    if(is[v]||c>1) last[v]=v;
    else if(c==1) last[v]=l;
}

int skok1[N][20];
int pre1[N];
int post1[N];

void dfs2(int v,int o)
{
    pre1[v]=++c;
    skok1[v][0]=o;
    for(int i=1;i<20;i++) skok1[v][i]=skok1[skok1[v][i-1]][i-1];
    for(auto u:G3[v])
    {
        d2[u.st]=d2[v]+u.nd;
        dfs2(u.st,v);
    }
    post1[v]=++c;
}

int lca1(int u,int v)
{
    if(pre1[u]<=pre1[v]&&post1[u]>=post1[v]) return u;
    if(pre1[v]<=pre1[u]&&post1[v]>=post1[u]) return v;
    for(int i=19;i>=0;i--) if(!(pre1[skok1[u][i]]<=pre1[v]&&post1[skok1[u][i]]>=post1[v])) u=skok1[u][i];
    return skok1[u][0];
}

int U[N],V[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q>>t;
    int r1,r2,p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) r1=i;
        else G1[p].pb(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) r2=i;
        else G2[p].pb(i);
    }
    dfs(r1,r1);
    cout<<endl;
    dfs1(r2);
    cout<<"!"<<endl;
    for(auto c:xd)
    {
        int u=c.st.st,v=c.st.nd,x=c.nd;
        int d1,d2,d3,d4;
        cin>>d1>>d2>>d3>>d4;
        int l=lca(u,v);
        X[l].pb({u,d1});
        X[u].pb({l,d1});
        X[l].pb({v,d2});
        X[v].pb({l,d2});
        if(v!=x) G3[x].pb({v,d4});
        G3[x].pb({u,d3});
    }
    c=0;
    dfs2(last[r2],last[r2]);
    deque<int>Q;
    Q.pb(r1);
    odw[r1]=1;
    while(sz(Q)>0)
    {
        int v=Q[0];
        Q.pop_front();
        for(auto x:X[v])
        {
            if(odw[x.st]) continue;
            odw[x.st]=1;
            Q.pb(x.st);
            if(pre[x.st]>=pre[v]) d1[x.st]=d1[v]+x.nd;
            else d1[x.st]=d1[v]-x.nd;
        }
    }
    for(int i=1;i<=t;i++) cin>>U[i]>>V[i];
    for(int i=1;i<=t;i++)
    {
        int u=U[i],v=V[i];
        int l=lca(u,v);
        cout<<d1[u]+d1[v]-2*d1[l]<<" ";
        l=lca1(u,v);
        cout<<d2[u]+d2[v]-2*d2[l]<<endl;
    }


    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:151:12: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |     odw[r1]=1;
      |     ~~~~~~~^~
Main.cpp:148:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |     dfs2(last[r2],last[r2]);
      |     ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 984 ms 358280 KB Output is correct
2 Correct 1129 ms 360972 KB Output is correct
3 Correct 860 ms 304412 KB Output is correct
4 Correct 854 ms 303984 KB Output is correct
5 Correct 922 ms 306092 KB Output is correct
6 Correct 1334 ms 316364 KB Output is correct
7 Correct 1206 ms 316468 KB Output is correct
8 Correct 1257 ms 315864 KB Output is correct
9 Correct 841 ms 304156 KB Output is correct
10 Correct 893 ms 305476 KB Output is correct
11 Correct 835 ms 302964 KB Output is correct
12 Correct 903 ms 305148 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1123 ms 360960 KB Output is correct
2 Correct 996 ms 357132 KB Output is correct
3 Runtime error 494 ms 250268 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 899 ms 308596 KB Output is correct
2 Correct 868 ms 308404 KB Output is correct
3 Runtime error 482 ms 249132 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1778 ms 436080 KB Output is correct
2 Correct 1769 ms 436464 KB Output is correct
3 Runtime error 949 ms 310488 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2078 ms 524172 KB Output is correct
2 Correct 2020 ms 523364 KB Output is correct
3 Runtime error 960 ms 311760 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -