oj.uz

Submission #1042718

# Submission time Handle Problem Language Result Execution time Memory
1042718 2024-08-03T10:06:09 Z SoulKnight Cat Exercise (JOI23_ho_t4) C++17
14 / 100
 2000 ms 980492 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const int N = 2e5 + 5;
const int INF = 1e9;

const int LG = 20;
int n, glit = 1, root, p[N], mx[LG][N], up[LG][N], where[N], what[N], sz[N];
vector<int> adj[N];

int dfs(int u, int par){
    up[0][u] = par;
    mx[0][glit] = u;

    where[u] = glit;
    what[glit] = u;
    glit++;

    int tot = 1;
    for (auto v: adj[u]){
        if (v == par) continue;
        tot += dfs(v, u);
    }
    sz[where[u]] = tot;
    return tot;
}

int answer(int l, int r){
    if (l > r) return 0;
    int lg = log2(r-l+1);
    return p[mx[lg][l]] > p[mx[lg][r-(1<<lg)+1]]? mx[lg][l]: mx[lg][r-(1<<lg)+1];
}

bool is_ancestor(int u, int v){
    return where[u] <= where[v] && where[v] <= where[u] + sz[where[u]] - 1;
}

int lca(int u, int v){
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i = LG-1; i >= 0; i--){
        if (!is_ancestor(up[i][u], v)) u = up[i][u];
    }
    return up[0][u];
}

ll dist(int u, int v){
    int ances = lca(u, v);
    ll ans = 0;
    for (int i = LG-1; i >= 0; i--){
        if (!is_ancestor(up[i][u], ances)) {ans += (1 << i); u = up[i][u];}
        if (!is_ancestor(up[i][v], ances)) {ans += (1 << i); v = up[i][v];}
    }

    return ans + (u != ances) + (v != ances);
}

struct Data{
    bool is_set;
    int lz, tm, mx, orig_mx;
    // -1 means invalidated
    // 0 means unchanged
    // 1 means re-overwrited

    int get(){
        if (lz == -1) return -INF;
        else return p[mx];
    }
};

#define lc (v << 1)
#define rc ((v << 1) + 1)

struct Seg{
    vector<Data> seg;
    int timer = 1;

    Seg(){
        seg.assign(4*(n+5), Data());
    }

    void pushup(int v){
        seg[v].mx = (seg[lc].get() > seg[rc].get()? seg[lc].mx: seg[rc].mx);
    }

    void pushdown(int v){
        if (!seg[v].is_set) return;

        if (seg[v].tm > seg[lc].tm){
            seg[lc].is_set = 1;
            seg[lc].tm = seg[v].tm;
            seg[lc].lz = seg[v].lz;

            if (seg[lc].lz == -1) seg[lc].mx = 0;
            else seg[lc].mx = seg[lc].orig_mx;
        }

        if (seg[v].tm > seg[rc].tm){
            seg[rc].is_set = 1;
            seg[rc].tm = seg[v].tm;
            seg[rc].lz = seg[v].lz;

            if (seg[rc].lz == -1) seg[rc].mx = 0;
            else seg[rc].mx = seg[rc].orig_mx;
        }

        seg[v].is_set = 0;
        seg[v].lz = 0;
        seg[v].tm = 0;
    }

    void build(int v=1, int tl=1, int tr=n){
        if (tl == tr){
            seg[v].orig_mx = seg[v].mx = what[tl];
            seg[v].lz = 0; seg[v].is_set = 0;
            seg[v].tm = 0;
            return;
        }

        int tm = (tl + tr) / 2;
        build(lc, tl, tm);
        build(rc, tm+1, tr);

        pushup(v);
        seg[v].orig_mx = seg[v].mx;
    }

    void upd(int l, int r, int mode, int v=1, int tl=1, int tr=n){
        if (tr < l || tl > r) return;
        if (l <= tl && tr <= r){
            // cout << "changing " << tl << ' ' << tr << ' ' << mode;
            seg[v].is_set = 1;
            seg[v].lz = mode;
            seg[v].tm = timer++; // it doesn't matter

            if (seg[v].lz == -1) seg[v].mx = 0;
            else seg[v].mx = seg[v].orig_mx;

            // cout << " to " << seg[v].mx << ln;

            return;
        }
        pushdown(v);
        int tm = (tl + tr) / 2;
        upd(l, r, mode, lc, tl, tm);
        upd(l, r, mode, rc, tm+1, tr);
        pushup(v);
    }

    array<int, 2> query(int l, int r, int v=1, int tl=1, int tr=n){
        if (tr < l || tl > r) return {-INF, 0}; // val, idx
        if (l <= tl && tr <= r) {
            return {seg[v].get(), seg[v].mx};
        }
        pushdown(v);
        int tm = (tl + tr) / 2;
        return max(query(l, r, lc, tl, tm),
                   query(l, r, rc, tm+1, tr));
    }
};


Seg seg = Seg();
int db = -1;


ll f(int u, int tp){
    // ++db;
    // cout << string(db, ' ') << u << ln;

    // if (u == 4){
    //     cout << seg.query(where[5], where[5] + sz[where[5]] - 1)[1] << ln;
    //     exit(0);
    // }

    int nxt;
    ll ans = 0;

    // go to subtree
    for (auto v: adj[u]){
        if (v == up[0][u]) continue;

        nxt = seg.query(where[v], where[v] + sz[where[v]] - 1)[1];
        if (nxt){
            seg.upd(where[tp], where[v]-1, -1);
            seg.upd(where[v] + sz[where[v]], where[tp] + sz[where[tp]] - 1, -1);
            // cout << where[v] + sz[where[v]] << ' ' << where[root] + sz[where[root]] - 1 << ln;
            // cout << seg.query(1, 1)[1] << ' ' << seg.query(3, 4)[1] << endl;
            // exit(0);

            ans = max(ans, dist(u, nxt) + f(nxt, v));

            seg.upd(where[tp], where[v]-1, 0);
            seg.upd(where[v] + sz[where[v]], where[tp] + sz[where[tp]] - 1, 0);

            // cout << seg.query(1, 1)[1] << ' ' << seg.query(3, 4)[1] << endl;
        }

        // cout << seg.query(3, 4)[1] << ln;
        // exit(0);
    }


    // go to above
    nxt = max(seg.query(where[tp], where[u] - 1),
              seg.query(where[u] + sz[where[u]], where[tp] + sz[where[tp]] - 1))[1];
    if (nxt){
        seg.upd(where[u], where[u] + sz[where[u]] - 1, -1);

        ans = max(ans, dist(u, nxt) + f(nxt, tp));

        seg.upd(where[u], where[u] + sz[where[u]] - 1, 0);
    }

    // --db;
    return ans;
}



void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    root = -1;
    for (int i = 1; i <= n; i++) if (p[i] == n) root = i;
    dfs(root, root);


    for (int i = 1; i < LG; i++){
        for (int j = 1; j <= n; j++) up[i][j] = up[i-1][up[i-1][j]];
        for (int j = 1; j + (1 << (i-1)) <= n; j++){
            mx[i][j] = (p[mx[i-1][j]] > p[mx[i-1][j + (1 << (i-1))]])? mx[i-1][j]: mx[i-1][j + (1 << (i-1))];
        }
    }

    seg.build();
    cout << f(root, root) << ln;




}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // int TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 2 ms 23148 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 2 ms 23148 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 3 ms 23128 KB Output is correct
12 Correct 2 ms 23132 KB Output is correct
13 Correct 3 ms 23132 KB Output is correct
14 Correct 3 ms 23132 KB Output is correct
15 Correct 3 ms 23132 KB Output is correct
16 Correct 2 ms 23196 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 2 ms 23148 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 3 ms 23128 KB Output is correct
12 Correct 2 ms 23132 KB Output is correct
13 Correct 3 ms 23132 KB Output is correct
14 Correct 3 ms 23132 KB Output is correct
15 Correct 3 ms 23132 KB Output is correct
16 Correct 2 ms 23196 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Execution timed out 2050 ms 980492 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 2 ms 23148 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 3 ms 23128 KB Output is correct
12 Correct 2 ms 23132 KB Output is correct
13 Correct 3 ms 23132 KB Output is correct
14 Correct 3 ms 23132 KB Output is correct
15 Correct 3 ms 23132 KB Output is correct
16 Correct 2 ms 23196 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Execution timed out 2050 ms 980492 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 2 ms 23148 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 3 ms 23128 KB Output is correct
12 Correct 2 ms 23132 KB Output is correct
13 Correct 3 ms 23132 KB Output is correct
14 Correct 3 ms 23132 KB Output is correct
15 Correct 3 ms 23132 KB Output is correct
16 Correct 2 ms 23196 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Execution timed out 2050 ms 980492 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Execution timed out 2077 ms 229804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 23132 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 3 ms 23132 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 2 ms 23148 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 3 ms 23128 KB Output is correct
12 Correct 2 ms 23132 KB Output is correct
13 Correct 3 ms 23132 KB Output is correct
14 Correct 3 ms 23132 KB Output is correct
15 Correct 3 ms 23132 KB Output is correct
16 Correct 2 ms 23196 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Execution timed out 2050 ms 980492 KB Time limit exceeded
19 Halted 0 ms 0 KB -