Submission #726905

#	Time	Username	Problem	Language	Result	Execution time	Memory
726905		MadokaMagicaFan	Prize (CEOI22_prize)	C++14	100 / 100	2093 ms	312908 KiB

Main

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
const ll inf = 1e9;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define endl                        '\n'

#define fst                         first
#define scn                         second
#define ONPC

vi sp;

void
ask(int a, int b)
{
    printf("? %d %d\n", a, b);
}

struct tree{
    vi p;
    vi d;
    vi et;
    vi in;
    vi f;
    int root;
    int n;
    vector<vi> adj;
    vector<vector<array<int,2>>> sdj;
    vector<ll> paiu;
    vector<bool> vis;

    tree(int _n)
    {
        n = _n;
        p.assign(n,0);
        d.assign(n,0);
        paiu.assign(n,0);
        d[0] = n+5;
        in.assign(n,0);
        adj.assign(n,{});
        sdj.assign(n,{});
        vis.assign(n,0);
    }

    void
    build()
    {
        for (int i = 1; i < n; ++i)
            if (p[i] == -1)
                root = i;

        for (int i = 1; i < n; ++i) {
            if (p[i] == -1) continue;
            /* adj[i].pb(p[i]); */
            adj[p[i]].pb(i);
        }

        dfs1(root);
        f.assign(4*sz(et), 0);
        build_aint(1,0,sz(et)-1);
        return;
    }

    void
    dfs1(int x)
    {
        in[x] = sz(et);
        et.pb(x);
        for (int u : adj[x]) {
            d[u] = d[x]+1;
            dfs1(u);
            et.pb(x);
        }
        return;
    }

    int
    merge_aint(int a, int b)
    {
        if (d[a] > d[b]) return b;
        return a;
    }

    int
    build_aint(int i, int l, int r)
    {
        int mid = (l+r)>>1;
        if (l == r) {
            f[i] = et[l];
            return f[i];
        }

        f[i] = merge_aint(
                build_aint(i<<1, l, mid),
                build_aint(i<<1|1, mid+1, r));
        return f[i];
    }

    int
    query_aint(int i, int l, int r, int tl, int tr)
    {
        int mid = (l+r)>>1;
        if (tr < l || r < tl) return 0;
        if (tl <= l && r <= tr) return f[i];
        int a1 = query_aint(i<<1, l, mid, tl, tr);
        int a2 = query_aint(i<<1|1, mid+1, r, tl, tr);
        return merge_aint(a1,a2);
        return merge_aint(
            query_aint(i<<1, l, mid, tl, tr),
            query_aint(i<<1|1, mid+1, r, tl, tr));
    }

    int
    lca(int a, int b)
    {
        if (in[a] > in[b]) swap(a,b);
        return query_aint(1, 0, sz(et)-1,in[a], in[b]);
    }

    int
    getnodes(int x, int k)
    {
        if (!k) return 0; /* Useless */
        --k; sp.pb(x);
        for (int u : adj[x]) {
            if (!k) return 0;
            k = getnodes(u,k);
        }
        return k;
    }

    void
    dfs2(int x, ll v)
    {
        if (vis[x]) return;
        vis[x] = 1;
        paiu[x]=v;

        for (auto u : sdj[x])
            dfs2(u[0], u[1]+v);
    }

    ll
    dist(int a, int b)
    {
        return paiu[a] + paiu[b] - 2ll*paiu[lca(a,b)];
    }
};


#ifdef ONPC
void
solve()
{
    int n, k, q, t;
    scanf("%d %d %d %d", &n, &k, &q, &t);
    tree t1(n+1), t2(n+1);
    for (int i = 0; i < n; ++i) scanf("%d", &t1.p[i+1]);
    for (int i = 0; i < n; ++i) scanf("%d", &t2.p[i+1]);

    t1.build();
    t2.build();

    t1.getnodes(t1.root, k);

    printf("%d", sp[0]);
    for (int i = 1; i < k; ++i) printf(" %d", sp[i]);
    printf("\n");

    vector<array<int, 2>> qq;

    for (int i = 0; i < k; ++i) {
        qq.pb({t2.in[sp[i]], sp[i]});
    }


    sort(qq.begin(), qq.end());

    for (int i = 0; i < k-1; ++i)
        ask(qq[i][1], qq[i+1][1]);
    printf("!\n");
    fflush(stdout);

    int d1, d2, lc;
    int a, b;
    for (int i = 0; i < k-1; ++i) {
        scanf("%d %d %d %d", &d1, &d2, &a, &b);
        lc = t1.lca(qq[i][1], qq[i+1][1]);
        if (lc != qq[i][1]) t1.sdj[lc].pb({qq[i][1], d1}); 
        if (lc != qq[i][1]) t1.sdj[qq[i][1]].pb({lc,-d1});
        if (lc != qq[i+1][1]) t1.sdj[lc].pb({qq[i+1][1], d2}); 
        if (lc != qq[i+1][1]) t1.sdj[qq[i+1][1]].pb({lc,-d2});

        d1 = a;
        d2 = b;
        lc = t2.lca(qq[i][1], qq[i+1][1]);
        if (lc != qq[i][1]) t2.sdj[lc].pb({qq[i][1], d1}); 
        if (lc != qq[i][1]) t2.sdj[qq[i][1]].pb({lc,-d1});
        if (lc != qq[i+1][1]) t2.sdj[lc].pb({qq[i+1][1], d2}); 
        if (lc != qq[i+1][1]) t2.sdj[qq[i+1][1]].pb({lc,-d2});
    }

    t1.dfs2(qq[0][1], 0);
    t2.dfs2(qq[0][1], 0);

    vector<array<ll,2>> ans;
    for (int i = 0; i < t; ++i) {
        scanf("%d %d", &d1, &d2);
        ans.pb({t1.dist(d1, d2), t2.dist(d1,d2)});
    }

    for (int i = 0; i < t; ++i) {
        printf("%lld %lld\n", ans[i][0], ans[i][1]);
    }
    fflush(stdout);
}

int32_t
main(int argc, char **argv)
{
    if (argc>1)
        freopen(argv[1], "r", stdin);
    solve();
}
#endif

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |     scanf("%d %d %d %d", &n, &k, &q, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:166:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     for (int i = 0; i < n; ++i) scanf("%d", &t1.p[i+1]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:167:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     for (int i = 0; i < n; ++i) scanf("%d", &t2.p[i+1]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:195:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         scanf("%d %d %d %d", &d1, &d2, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:216:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         scanf("%d %d", &d1, &d2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int32_t main(int, char**)':
Main.cpp:230:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |         freopen(argv[1], "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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