Submission #1227875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227875		12345678	Prize (CEOI22_prize)	C++20	0 / 100	3577 ms	259724 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, k, q, T, tmp, x, y, u, v, cnt, qu[nx], qv[nx];

struct tree
{
    int rt, rtg, p[nx], t, in[nx], out[nx], sz[nx], hd[nx], lvl[nx], on[nx], dist[nx];
    vector<tuple<int, int, int, int, int>> qrs;
    vector<int> d[nx];
    vector<pair<int, int>> g[nx];
    void init()
    {
        for (int i=1; i<=n; i++)
        {
            cin>>p[i];
            if (p[i]==-1) rt=i;
            else d[p[i]].push_back(i);
        }
        dfs(rt);
        hld(rt, rt);
        vector<pair<int, int>> srt;
        for (int i=1; i<=k; i++) on[i]=1, srt.push_back({in[i], i});
        sort(srt.begin(), srt.end());
        for (int i=1; i<k; i++) on[lca(srt[i-1].second, srt[i].second)]=1;
        srt.clear();
        for (int i=1; i<=n; i++) if (on[i]) srt.push_back({in[i], i});
        sort(srt.begin(), srt.end());
        stack<int> s;
        for (auto [_, u]:srt)
        {
            if (!rtg)
            {
                rtg=u;
                s.push(u);
                continue;
            }
            //cout<<"u "<<u<<endl;
            while (!(in[s.top()]<=in[u]&&out[u]<=out[s.top()])) s.pop();
            g[s.top()].push_back({u, 0});
            s.push(u);
        }
        dfs2(rtg);
    }
    void init2()
    {
        dfsg(rtg);
    }
    void dfs(int u)
    {
        sz[u]=1;
        in[u]=++t;
        for (auto v:d[u]) lvl[v]=lvl[u]+1, dfs(v), sz[u]+=sz[v];
        out[u]=t;
    }
    void dfs2(int u)
    {
        for (auto [v, w]:g[u]) dfs2(v);
        if (g[u].empty()) return;
        for (int i=0; i<g[u].size(); i+=2)
        {
            if (i==g[u].size()-1) qrs.push_back({u, g[u][i].first, u, i, 0});
            else qrs.push_back({g[u][i].first, g[u][i+1].first, u, i, 1});
        }
    }
    void dfsg(int u)
    {
        for (auto [v, w]:g[u]) dist[v]=dist[u]+w, dfsg(v);
    }
    void hld(int u, int h)
    {
        hd[u]=h;
        pair<int, int> hv;
        for (auto v:d[u]) hv=max(hv, {sz[v], v});
        if (hv.second) hld(hv.second, h);
        for (auto v:d[u]) if (v!=hv.second) hld(v, v);
    }
    int lca(int u, int v)
    {
        while (hd[u]!=hd[v])
        {
            if (lvl[hd[u]]>lvl[hd[v]]) swap(u, v);
            v=p[hd[v]];
        }
        if (lvl[u]>lvl[v]) swap(u, v);
        return u;
    }
    int query(int u, int v)
    {
        return dist[u]-dist[lca(u, v)]+dist[v]-dist[lca(u, v)];
    }
} t1, t2;

int main()
{
    cin>>n>>k>>q>>T;
    t1.init();
    t2.init();
    for (int i=1; i<=k; i++) cout<<i<<' ';
    cout<<endl;
    for (auto [u, v, _a, _b, _c]:t1.qrs) cout<<"? "<<u<<' '<<v<<'\n';
    for (auto [u, v, _a, _b, _c]:t2.qrs) cout<<"? "<<u<<' '<<v<<'\n';
    cout<<"!"<<endl;
    for (auto [_a, _b, u, i, t]:t1.qrs)
    {
        cin>>x>>y>>tmp>>tmp;
        if (!t) t1.g[u][i].second=y;
        else t1.g[u][i].second=x, t1.g[u][i+1].second=y;
    }
    for (auto [_a, _b, u, i, t]:t2.qrs)
    {
        cin>>tmp>>tmp>>x>>y;
        if (!t) t2.g[u][i].second=y;
        else t2.g[u][i].second=x, t2.g[u][i+1].second=y;
    }
    t1.init2();
    t2.init2();
    for (int i=0;i <T; i++) cin>>qu[i]>>qv[i];
    for (int i=0; i<T; i++) cout<<t1.query(qu[i], qv[i])<<' '<<t2.query(qu[i], qv[i])<<'\n';
}

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