oj.uz

답안 #653377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653377 2022-10-26T16:32:58 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 2626 ms 393120 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=1000007;

bool is[N];
int n,k,q,t;

struct tree
{
    vector<int>G[N];
    int pre[N];
    int post[N];
    int root;
    int skok[N][20];
    int d[N];
    vector<pair<int,int>>X[N];
    bool odw[N];
    int c=0;
    void dfs_lca(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];
        for(auto u:G[v]) dfs_lca(u,v);
        post[v]=++c;
    }
    bool anc(int u,int v)
    {
        return pre[u]<=pre[v]&&post[u]>=post[v];
    }
    int lca(int u,int v)
    {
        if(anc(u,v)) return u;
        if(anc(v,u)) return v;
        for(int i=19;i>=0;i--) if(!anc(skok[u][i],v)) u=skok[u][i];
        return skok[u][0];
    }
    void get_d()
    {
        for(int i=1;i<=n;i++) odw[i]=0;
        odw[root]=1;
        d[root]=0;
        deque<int>Q;
        Q.pb(root);
        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]) d[x.st]=d[v]+x.nd;
                else d[x.st]=d[v]-x.nd;
            }
        }
    }
};

tree T1,T2;

void dfs_k(int v)
{
    if(k>0)
    {
        cout<<v<<" ";
        is[v]=1;
        k--;
    }
    for(auto u:T1.G[v]) dfs_k(u);
}

vector<int>V;

void dfs1(int v)
{
    if(is[v]) V.pb(v);
    for(auto u:T2.G[v]) dfs1(u);
}

int A[N],B[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q>>t;
    int K=k,p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) T1.root=i;
        else T1.G[p].pb(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) T2.root=i;
        else T2.G[p].pb(i);
    }
    dfs_k(T1.root);
    cout<<endl;
    T1.dfs_lca(T1.root,T1.root);
    T2.dfs_lca(T2.root,T2.root);
    dfs1(T2.root);
    for(int i=1;i<K;i++) cout<<"? "<<V[i-1]<<" "<<V[i]<<endl;
    cout<<"!"<<endl;
    for(int i=1;i<K;i++)
    {
        int u=V[i-1],v=V[i];
        int d1,d2,d3,d4;
        cin>>d1>>d2>>d3>>d4;
        int l=T1.lca(u,v);
        T1.X[l].pb({u,d1});
        T1.X[u].pb({l,d1});
        T1.X[l].pb({v,d2});
        T1.X[v].pb({l,d2});
        l=T2.lca(u,v);
        T2.X[l].pb({u,d3});
        T2.X[u].pb({l,d3});
        T2.X[l].pb({v,d4});
        T2.X[v].pb({l,d4});
    }
    T1.get_d();
    T2.get_d();
    for(int i=1;i<=t;i++) cin>>A[i]>>B[i];
    for(int i=1;i<=t;i++)
    {
        int u=A[i],v=B[i];
        int l=T1.lca(u,v);
        cout<<T1.d[u]+T1.d[v]-2*T1.d[l]<<" ";
        l=T2.lca(u,v);
        cout<<T2.d[u]+T2.d[v]-2*T2.d[l]<<endl;
    }


    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1578 ms 247768 KB Output is correct
2 Correct 1488 ms 250356 KB Output is correct
3 Correct 1117 ms 210220 KB Output is correct
4 Correct 1154 ms 209776 KB Output is correct
5 Correct 1200 ms 212432 KB Output is correct
6 Correct 1975 ms 219652 KB Output is correct
7 Correct 1855 ms 219548 KB Output is correct
8 Correct 1559 ms 218736 KB Output is correct
9 Correct 1086 ms 209980 KB Output is correct
10 Correct 1082 ms 211692 KB Output is correct
11 Correct 1185 ms 208836 KB Output is correct
12 Correct 1133 ms 211220 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1420 ms 248744 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1121 ms 237688 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2612 ms 382388 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2626 ms 393120 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -