oj.uz

Submission #1085100

# Submission time Handle Problem Language Result Execution time Memory
1085100 2024-09-07T13:59:17 Z shiocan Prize (CEOI22_prize) C++17
100 / 100
 2817 ms 591380 KB 
#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
    #define cin fin
    #define cout fout
    string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long 
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7; 
const int inf = 1e18;
const int N = 1e6 + 10, K = 20;

struct tree{
    vector<pii> a[N];
    vector<int> g[N];
    int up[N][K], dp[N], tin[N], depth[N];
    vector<int> pre;

    int root = -1;

    int timein = 0;
    void dfs(int u, int p){
        up[u][0] = p;
        pre.push_back(u);
        depth[u] = depth[p] + 1;
        tin[u] = ++timein;

        for(int j = 1; j < K; j++)
            up[u][j] = up[up[u][j - 1]][j - 1];

        for(auto i : g[u])
            if(i != p){
                dfs(i, u);
            }
    }

    int lca(int u, int v){
        if(depth[u] > depth[v])
            swap(u, v);

        for(int j = K - 1; j >= 0; j--)
            if(depth[u] <= depth[up[v][j]]) 
                v = up[v][j];

        if(u == v)
            return u;

        for(int j = K - 1; j >= 0; j--)
            if(up[u][j] != up[v][j])
                u = up[u][j], v = up[v][j];

        return up[u][0];
    }

    void add(int u, int v, int w1, int w2){
        int l = lca(u, v);

        if(root == -1 || depth[l] < depth[root])
            root = l;

        a[l].push_back({u, w1});
        a[u].push_back({l, w1});
        a[l].push_back({v, w2});
        a[v].push_back({l, w2});
    }

    void solve(){
        queue<int> q;
        q.push(root);

        while(!q.empty()){
            int s = q.front();
            q.pop();

            for(auto [u, w] : a[s]){
                if(dp[u] == 0 && u != s && u != root)
                    dp[u] = dp[s] + (depth[u] >= depth[s] ? w : -w), q.push(u);
            }
        }
    }

    int query(int u, int v){
        int l = lca(u, v);
        return dp[u] + dp[v] - (2 * dp[l]);
    }
}a1, a2;

int n, k, q, t;

void solve(){       
    cin >> n >> k >> q >> t;


    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;

        if(x == -1)
            a1.root = i;
        else{
            a1.g[x].push_back(i);
            a1.g[i].push_back(x);
        }
    }

    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;

        if(x == -1)
            a2.root = i;
        else{
            a2.g[x].push_back(i);
            a2.g[i].push_back(x);
        }
    }

    a1.dfs(a1.root, a1.root);
    a2.dfs(a2.root, a2.root);

    vector<int> aux;
    for(int i = 0; i < k; i++)
        aux.push_back(a1.pre[i]);

    for(auto i : aux)
        cout << i << ' ';
    cout << endl;

    sort(all(aux), [&] (int i, int j){
        return a2.tin[i] < a2.tin[j];
    });

    for(int i = 0; i < k - 1; i++)
        cout << "? " << aux[i] << ' ' << aux[i + 1] << '\n';
    cout << "!" << endl;

    a1.root = a2.root = -1;

    for(int i = 0; i < k - 1; i++){
        int w1, w2, w3, w4;
        cin >> w1 >> w2 >> w3 >> w4;

        a1.add(aux[i], aux[i + 1], w1, w2);
        a2.add(aux[i], aux[i + 1], w3, w4);
    }

    a1.solve();
    a2.solve();

    vector<pii> ans;

    for(int i = 0; i < t; i++){
        int x, y;
        cin >> x >> y;

        ans.push_back({a1.query(x, y), a2.query(x, y)});
    }

    for(auto i : ans)
        cout << i.first << ' ' << i.second << '\n';
    cout << endl;
}

int32_t main(){ 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 347724 KB Output is correct
2 Correct 1362 ms 351640 KB Output is correct
3 Correct 1078 ms 335896 KB Output is correct
4 Correct 1012 ms 335108 KB Output is correct
5 Correct 961 ms 339404 KB Output is correct
6 Correct 1196 ms 340008 KB Output is correct
7 Correct 1196 ms 339620 KB Output is correct
8 Correct 1208 ms 338212 KB Output is correct
9 Correct 848 ms 335748 KB Output is correct
10 Correct 874 ms 338828 KB Output is correct
11 Correct 964 ms 333432 KB Output is correct
12 Correct 958 ms 338052 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1446 ms 351956 KB Output is correct
2 Correct 1172 ms 345228 KB Output is correct
3 Correct 961 ms 335448 KB Output is correct
4 Correct 998 ms 339432 KB Output is correct
5 Correct 1073 ms 336732 KB Output is correct
6 Correct 1550 ms 336052 KB Output is correct
7 Correct 1421 ms 340888 KB Output is correct
8 Correct 1443 ms 341408 KB Output is correct
9 Correct 1267 ms 342064 KB Output is correct
10 Correct 1272 ms 343332 KB Output is correct
11 Correct 1207 ms 337780 KB Output is correct
12 Correct 1227 ms 343364 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 328072 KB Output is correct
2 Correct 837 ms 328148 KB Output is correct
3 Correct 644 ms 315520 KB Output is correct
4 Correct 651 ms 315504 KB Output is correct
5 Correct 755 ms 315384 KB Output is correct
6 Correct 796 ms 317792 KB Output is correct
7 Correct 836 ms 317824 KB Output is correct
8 Correct 873 ms 317840 KB Output is correct
9 Correct 803 ms 318528 KB Output is correct
10 Correct 850 ms 318620 KB Output is correct
11 Correct 752 ms 318588 KB Output is correct
12 Correct 746 ms 318488 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2116 ms 565664 KB Output is correct
2 Correct 2142 ms 565684 KB Output is correct
3 Correct 1554 ms 540988 KB Output is correct
4 Correct 1706 ms 540772 KB Output is correct
5 Correct 1608 ms 540724 KB Output is correct
6 Correct 2089 ms 545352 KB Output is correct
7 Correct 1904 ms 545524 KB Output is correct
8 Correct 1966 ms 546580 KB Output is correct
9 Correct 1757 ms 547420 KB Output is correct
10 Correct 1769 ms 547052 KB Output is correct
11 Correct 1829 ms 546836 KB Output is correct
12 Correct 2013 ms 547604 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2817 ms 591380 KB Output is correct
2 Correct 2695 ms 589872 KB Output is correct
3 Correct 1940 ms 559668 KB Output is correct
4 Correct 1946 ms 565992 KB Output is correct
5 Correct 1829 ms 558696 KB Output is correct
6 Correct 2627 ms 571536 KB Output is correct
7 Correct 2403 ms 563712 KB Output is correct
8 Correct 2471 ms 567744 KB Output is correct
9 Correct 2350 ms 568192 KB Output is correct
10 Correct 2290 ms 566292 KB Output is correct
11 Correct 2517 ms 566424 KB Output is correct
12 Correct 2355 ms 570228 KB Output is correct