oj.uz

Submission #971392

# Submission time Handle Problem Language Result Execution time Memory
971392 2024-04-28T13:03:11 Z vjudge1 Prize (CEOI22_prize) C++17
0 / 100
 1770 ms 356332 KB 
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct tree {
    int n; 
    vi par, niv, D;
    vector<vi> L, Anc;

    tree(int N) : n(N), L(N), par(N), niv(N) {}

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void set_dist(vi dist0) { D = dist0; }

    void init() {
        function<void(int, int, int)> dfs0 = [&](int u, int p, int li) {
            par[u] = p;
            niv[u] = li;
            for(auto it : L[u])
                if(it != p)  {
                    dfs0(it, u, li + 1);
                }
        };
        dfs0(0, -1, 0);
        Anc.push_back(par);
        for(int k = 1; (1 << k) <= n; ++k) {
            Anc.push_back(Anc.back());
            for(int i = 0; i < n; ++i)
                Anc[k][i] = Anc[k - 1][i] == -1 ? -1 : Anc[k - 1][Anc[k - 1][i]];
        }
    }

    int lift(int u, int nr) {
        for(int i = 0; i < Anc.size(); ++i)
            if(nr & (1 << i)) u = Anc[i][u];
        return u;
    }

    int lca(int u, int v) {
        if(niv[u] > niv[v]) swap(u, v);
        v = lift(v, niv[v] - niv[u]);
        if(u == v) return u;
        for(int i = int(Anc.size()) - 1; i >= 0; --i)
            if(Anc[i][u] != Anc[i][v]) {
                u = Anc[i][u];
                v = Anc[i][v];
            }
        return par[u];
    }

    int dist(int u, int v) {
        int l = lca(u, v);
        return D[u] + D[v] - 2 * D[l];
    }

    vi get_V(int k) {
        vi Re;
        function<void(int, int)> dfs = [&](int u, int p) {
            if(!k) return;
            Re.push_back(u);
            --k;
            for(auto it : L[u])
                if(it != p) {
                    dfs(it, u);
                }
        };
        dfs(0, -1);
        return Re;
    }
};
int main() {
    int n, k, q, t;
    cin >> n >> k >> q >> t;

    tree T1(n), T2(n);
    for(int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        if(p != -1) T1.add_edge(i, p - 1);
    }
    for(int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        if(p != -1) T2.add_edge(i, p - 1);
    }
    T1.init();
    T2.init();

    auto V = T1.get_V(k);
    for(auto it : V)
        cout << it + 1 << " ";
    cout << "\n";
    vi dist(n, 0);
    for(int i = 1; i < V.size(); ++i) {
        cout << "? " << V[0] + 1 << " " << V[i] + 1 << endl;
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        dist[V[i]] = a + b;
    }
    T1.set_dist(dist);

    for(int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        cout << T1.dist(a, b) << "\n";
    }

    return 0;
}

Compilation message

Main.cpp: In constructor 'tree::tree(int)':
Main.cpp:11:16: warning: 'tree::L' will be initialized after [-Wreorder]
   11 |     vector<vi> L, Anc;
      |                ^
Main.cpp:10:8: warning:   'vi tree::par' [-Wreorder]
   10 |     vi par, niv, D;
      |        ^~~
Main.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     tree(int N) : n(N), L(N), par(N), niv(N) {}
      |     ^~~~
Main.cpp: In member function 'int tree::lift(int, int)':
Main.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0; i < Anc.size(); ++i)
      |                        ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 1; i < V.size(); ++i) {
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 858 ms 174780 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 858 ms 183412 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 792 ms 178756 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1770 ms 349800 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1755 ms 356332 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -