oj.uz

Submission #1085092

# Submission time Handle Problem Language Result Execution time Memory
1085092 2024-09-07T13:48:33 Z shiocan Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 687108 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; 

struct tree{
    int n;
    vector<vector<pii>> a;
    vector<vector<int>> g, up;
    vector<int> pre, depth, tin, dp;

    int root = -1;

    tree(int _n){
        n = _n + 5;

        a = vector<vector<pii>> (n);
        g = vector<vector<int>> (n);
        depth = tin = dp = vector<int> (n, 0ll);
        up = vector<vector<int>> (n, vector<int> (22));
    }

    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 < 22; 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 = 21; j >= 0; j--)
            if(depth[u] <= depth[up[v][j]]) 
                v = up[v][j];

        if(u == v)
            return u;

        for(int j = 21; 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]);
    }
};

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

    tree a1(n), a2(n);

    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 2049 ms 355856 KB Output is correct
2 Correct 2151 ms 360368 KB Output is correct
3 Correct 1117 ms 344392 KB Output is correct
4 Correct 1081 ms 343104 KB Output is correct
5 Correct 1211 ms 347112 KB Output is correct
6 Correct 1669 ms 348028 KB Output is correct
7 Correct 1638 ms 347388 KB Output is correct
8 Correct 1730 ms 346184 KB Output is correct
9 Correct 1319 ms 343336 KB Output is correct
10 Correct 1295 ms 346276 KB Output is correct
11 Correct 1179 ms 341176 KB Output is correct
12 Correct 1241 ms 345732 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2312 ms 360732 KB Output is correct
2 Correct 2011 ms 354012 KB Output is correct
3 Correct 1153 ms 343152 KB Output is correct
4 Correct 1227 ms 347800 KB Output is correct
5 Correct 1227 ms 344672 KB Output is correct
6 Correct 1665 ms 344252 KB Output is correct
7 Correct 1759 ms 349616 KB Output is correct
8 Correct 1767 ms 350144 KB Output is correct
9 Correct 1482 ms 350024 KB Output is correct
10 Correct 1514 ms 351324 KB Output is correct
11 Correct 1547 ms 345936 KB Output is correct
12 Correct 1578 ms 351076 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1548 ms 343668 KB Output is correct
2 Correct 1540 ms 343656 KB Output is correct
3 Correct 855 ms 329748 KB Output is correct
4 Correct 866 ms 329616 KB Output is correct
5 Correct 906 ms 329748 KB Output is correct
6 Correct 1140 ms 332020 KB Output is correct
7 Correct 1201 ms 332104 KB Output is correct
8 Correct 1183 ms 332252 KB Output is correct
9 Correct 1006 ms 332428 KB Output is correct
10 Correct 1080 ms 332568 KB Output is correct
11 Correct 1035 ms 332472 KB Output is correct
12 Correct 1022 ms 332512 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3555 ms 687064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3553 ms 687108 KB Time limit exceeded
2 Halted 0 ms 0 KB -