oj.uz

Submission #971409

# Submission time Handle Problem Language Result Execution time Memory
971409 2024-04-28T13:16:38 Z vjudge1 Prize (CEOI22_prize) C++17
10 / 100
 1818 ms 386856 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

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() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    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";
    cout.flush();
    vi dist(n, 0);
    for(int i = 1; i < V.size(); ++i) {
        cout << "? " << V[0] + 1 << " " << V[i] + 1 << endl;
    }
    cout << "!" << endl;
    for(int i = 1; i < V.size(); ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        dist[V[i]] = a + b;
    }
    cout.flush();
    T1.set_dist(dist);

    vi Re;
    for(int i = 0; i < t; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        int v = T1.dist(a, b);
        Re.push_back(v);
    }
    for(auto it : Re)
        cout << it << " " << it << "\n";
    cout.flush();
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 190412 KB Output is correct
2 Correct 1127 ms 200140 KB Output is correct
3 Correct 935 ms 144864 KB Output is correct
4 Correct 884 ms 144852 KB Output is correct
5 Correct 954 ms 145024 KB Output is correct
6 Correct 1008 ms 152644 KB Output is correct
7 Correct 960 ms 151380 KB Output is correct
8 Correct 961 ms 149704 KB Output is correct
9 Correct 920 ms 144848 KB Output is correct
10 Correct 921 ms 145292 KB Output is correct
11 Correct 844 ms 145044 KB Output is correct
12 Correct 876 ms 144932 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 935 ms 201460 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 732 ms 196228 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1706 ms 378864 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1818 ms 386856 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -