제출 #1173508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173508		Syrius	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	510 ms	105300 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;

const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
const int lg = 20;

vector < vint > adj(mxn);
int n;
int a[mxn] , p[mxn];
int lev[mxn] , tab[lg][mxn];
int in[mxn] , out[mxn];
int rev[mxn];
int timer = 0;

void tour(int u , int par) {
    in[u] = ++timer;
    a[timer] = p[u];
    rev[timer] = u;

    for (int v : adj[u]) {
        if (v == par) continue;
        tour(v , u);
    }

    out[u] = timer;
}

struct node {

    int tl , tm , tr;
    int id;
    bool lz;
    node *left , *right;    

    node (int l , int r) {
        tl = l , tr = r , tm = (l + r) / 2;
        lz = 0;
        if (tl == tr) {
            id = tl;
            return;
        }
        left = new node(tl , tm);
        right = new node(tm+1 , tr);
        id = (a[left->id] > a[right->id]) ? left->id : right->id;
    }

    int querrrry(int l , int r) {
        if (tl == l && tr == r) return id;
        if (r <= tm) return left -> querrrry(l , r);
        else if (l > tm) return right -> querrrry(l , r);
        
        int idl = left -> querrrry(l , tm);
        int idr = right -> querrrry(tm+1 , r);
        return (a[idl] > a[idr]) ? idl : idr;
    }

    int query(int l , int r) {
        return rev[querrrry(l , r)];
    }

    void pro() {
        if (lz == 0) return;
        left -> lz = right -> lz = 1;
        left -> id = right -> id = 0;
        lz = 0;
    }

    void update(int l , int r) {
        if (tl == l && tr == r) {
            lz = 1;
            id = 0;
            return;
        }
        pro();
        if (r <= tm) left -> update(l , r);
        else if (l > tm) right -> update(l , r);
        else {
            left -> update(l , tm);
            right -> update(tm+1 , r);
        }
        id = (a[left->id] > a[right->id]) ? left->id : right->id;
    }

} *root;

void setlev(int u , int par , int lv) {
    lev[u] = lv;
    tab[0][u] = par;
    for (int v : adj[u]) {
        if (v == par) continue;
        setlev(v , u , lv+1);
    }
}

void build(int st) {
    setlev(st , st , 0);
    for (int i = 1; i < lg; i++) {
        for (int j = 1; j <= n; j++) {
            tab[i][j] = tab[i-1][tab[i-1][j]];
        }
    }
}

int dis(int a , int b) {
    if (lev[b] < lev[a]) swap(a , b);
    int d = lev[b] - lev[a];

    for (int i = 0; i < lg; i++) {
        if (d & (1 << i)) b = tab[i][b];
    }

    if (a == b) return d;
    int ret = 0;
    for (int i = lg-1; i >= 0; i--) {
        if (tab[i][a] != tab[i][b]) {
            a = tab[i][a];
            b = tab[i][b];
            ret += (1 << i);
        }
    }

    return (ret + 1) * 2 + d;
}

int dfs(int u) {

    int ver = root -> query(in[u] , out[u]);
    if (ver == u) {
        root -> update(in[u] , in[u]);
        ver = root -> query(in[u] , out[u]);

        if (ver == 0) return 0;
        
        int result = 0;
        for (int v : adj[u]) {
            if (lev[v] < lev[u]) continue;
            result = max(result , dfs(v) + 1);
        }
        root -> update(in[u] , out[u]);
        return result;
    }

    // cout << u << ' ' << ver << '\n';
    if (ver == 0) return 0;

    // cout << "CONTINUING " << u << ' ' << ver << '\n';

    int ans = dfs(ver) + dis(u , ver);
    root -> update(in[ver] , out[ver]);
    
    // cout << "current answer is: " << ans << '\n';
    int ret = dis(u , ver);
    while (1) {
        int newver = root -> query(in[u] , out[u]);
        // cout << "CURRENTLY AT u = " << u << " BUT NEWVER IS:  " << newver << '\n';
        if (newver == 0) break;
        ret += dis(ver , newver);
        // cout << "RET: " << ret << '\n';
        ver = newver;
        // root -> update(in[ver] , in[ver]);
        ans = max(ans , ret + dfs(ver));
        root -> update(in[ver] , out[ver]);
        // cout << "current answer is: " << ans << '\n';
    }

    root -> update(in[u] , out[u]);
    return ans;
}

signed main() {

    cin >> n;

    int st = 1;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        if (p[i] == n) st = i;
    }

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

    build(st);
    tour(st , st);
    a[0] = -inf;

    root = new node(0 , n);

    cout << dfs(st) << '\n';
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26