제출 #1308341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308341		HoriaHaivas	Prize (CEOI22_prize)	C++20	10 / 100	1126 ms	165108 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

int p[3][500005];
int h[3][500005];
int pathsum[500005];
int ans[500005];
int up[19][500005];
vector<int> nodes[3][500005];
bool marked[500005];
queue<int> q;
vector<pair<int,int>> v;
map<pair<int,int>,int> mp;

struct ceva
{
    int unu;
    int doi;
    int trei;
    int patru;
};

void query(int a, int b)
{
    cout << "? "  <<  a << " " << b << endl;
    v.push_back({a,b});
}

void dfs(int node, int parent)
{
    for (auto x : nodes[1][node])
    {
        if (marked[x])
        {
            query(x,node);
            dfs(x,node);
        }
    }
}

void dfs2(int node, int parent)
{
    for (auto x : nodes[1][node])
    {
        if (marked[x])
        {
            h[1][x]=h[1][node]+1;
            pathsum[x]=pathsum[node]+mp[{node,x}];
            dfs2(x,node);
        }
    }
}

int lca(int a, int b)
{
    if (h[1][a]<h[1][b])
        swap(a,b);
    int k,i;
    k=h[1][a]-h[1][b];
    for (i=18; i>=0; i--)
    {
        if (k&(1<<i))
            a=up[i][a];
    }
    if (a==b)
        return a;
    for (i=18; i>=0; i--)
    {
        if (up[i][a]!=up[i][b])
        {
            a=up[i][a];
            b=up[i][b];
        }
    }
    return up[0][a];
}

int dist(int a, int b)
{
    int c;
    c=lca(a,b);
    return pathsum[a]+pathsum[b]-2*pathsum[c];
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ///ios_base::sync_with_stdio(0);
    ///cin.tie(0);
    ///cout.tie(0);
    int n,k,qq,t,i,root,a,b,fr,j,c,d;
    cin >> n >> k >> qq >> t;
    for (i=1; i<=n; i++)
    {
        cin >> p[1][i];
        if (p[1][i]==-1)
            root=i;
        else
            nodes[1][p[1][i]].push_back(i);
    }
    for (i=1; i<=n; i++)
    {
        cin >> p[2][i];
        if (p[2][i]!=-1)
            nodes[2][p[2][i]].push_back(i);
    }
    ///sub1
    q.push(root);
    while (k>0)
    {
        fr=q.front();
        marked[fr]=1;
        for (auto x : nodes[1][fr])
        {
            q.push(x);
        }
        k--;
        q.pop();
    }
    for (i=1; i<=n; i++)
    {
        if (marked[i])
            cout << i << " ";
    }
    cout << endl;
    cout.flush();
    pathsum[root]=0;
    h[1][root]=1;
    dfs(root,-1);
    cout << "!" << endl;
    cout.flush();
    for (i=0;i<v.size();i++)
    {
         cin >> a >> b >> c >> d;
         mp[{v[i].second,v[i].first}]=a;
    }
    dfs2(root,-1);
    for (i=1; i<=n; i++)
    {
        up[0][i]=p[1][i];
    }
    for (i=1; i<=18; i++)
    {
        for (j=1; j<=n; j++)
        {
            if (up[i-1][j]!=-1)
            up[i][j]=up[i-1][up[i-1][j]];
        }
    }
    for (i=1; i<=t; i++)
    {
        cin >> a >> b;
        ans[i]=dist(a,b);
    }
    for (i=1;i<=t;i++)
    {
         cout << ans[i] << " " << ans[i] << endl;
    }
    cout << endl;
    cout.flush();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24