oj.uz

Submission #726905

# Submission time Handle Problem Language Result Execution time Memory
726905 2023-04-19T14:05:56 Z MadokaMagicaFan Prize (CEOI22_prize) C++14
100 / 100
 2093 ms 312908 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 159964 KB Output is correct
2 Correct 1215 ms 161796 KB Output is correct
3 Correct 945 ms 132372 KB Output is correct
4 Correct 860 ms 132276 KB Output is correct
5 Correct 1012 ms 134392 KB Output is correct
6 Correct 1035 ms 139544 KB Output is correct
7 Correct 1054 ms 139408 KB Output is correct
8 Correct 1081 ms 138796 KB Output is correct
9 Correct 948 ms 132300 KB Output is correct
10 Correct 943 ms 133780 KB Output is correct
11 Correct 853 ms 131196 KB Output is correct
12 Correct 962 ms 133472 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1270 ms 161660 KB Output is correct
2 Correct 1123 ms 158836 KB Output is correct
3 Correct 981 ms 133548 KB Output is correct
4 Correct 1143 ms 136076 KB Output is correct
5 Correct 1079 ms 134408 KB Output is correct
6 Correct 1036 ms 138592 KB Output is correct
7 Correct 1197 ms 141364 KB Output is correct
8 Correct 1322 ms 141688 KB Output is correct
9 Correct 1147 ms 140128 KB Output is correct
10 Correct 1187 ms 140952 KB Output is correct
11 Correct 1108 ms 137552 KB Output is correct
12 Correct 1181 ms 140736 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 153100 KB Output is correct
2 Correct 726 ms 153156 KB Output is correct
3 Correct 588 ms 124024 KB Output is correct
4 Correct 641 ms 123980 KB Output is correct
5 Correct 539 ms 124236 KB Output is correct
6 Correct 664 ms 130920 KB Output is correct
7 Correct 644 ms 130884 KB Output is correct
8 Correct 655 ms 130808 KB Output is correct
9 Correct 612 ms 128664 KB Output is correct
10 Correct 606 ms 128692 KB Output is correct
11 Correct 599 ms 128776 KB Output is correct
12 Correct 617 ms 128764 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1808 ms 306128 KB Output is correct
2 Correct 1771 ms 306120 KB Output is correct
3 Correct 1217 ms 248064 KB Output is correct
4 Correct 1316 ms 248224 KB Output is correct
5 Correct 1262 ms 248100 KB Output is correct
6 Correct 1429 ms 261764 KB Output is correct
7 Correct 1421 ms 261648 KB Output is correct
8 Correct 1461 ms 261636 KB Output is correct
9 Correct 1346 ms 257532 KB Output is correct
10 Correct 1389 ms 257604 KB Output is correct
11 Correct 1415 ms 257416 KB Output is correct
12 Correct 1399 ms 257456 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2073 ms 312908 KB Output is correct
2 Correct 2093 ms 312472 KB Output is correct
3 Correct 1645 ms 255132 KB Output is correct
4 Correct 1688 ms 259020 KB Output is correct
5 Correct 1522 ms 254332 KB Output is correct
6 Correct 1928 ms 271608 KB Output is correct
7 Correct 1703 ms 267884 KB Output is correct
8 Correct 1802 ms 270120 KB Output is correct
9 Correct 1705 ms 265652 KB Output is correct
10 Correct 1647 ms 264732 KB Output is correct
11 Correct 1687 ms 264880 KB Output is correct
12 Correct 1762 ms 266840 KB Output is correct