Submission #1085100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085100		shiocan	Prize (CEOI22_prize)	C++17	100 / 100	2817 ms	591380 KiB

Main

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24