Submission #900213

#	Time	Username	Problem	Language	Result	Execution time	Memory
900213		HorizonWest	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	216 ms	51836 KiB

Main

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

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

vector <vector<int>> v;

struct LowerCommonAncestor
{
    vector <int> L, E, H; int idx, n;

    void dfs(int cur, int depth, int parent)
    {
        H[cur] = idx;
        E[idx] = cur;
        L[idx++] = depth;

        for (auto& u : v[cur]) if(u != parent)
        {
            dfs(u, depth + 1, cur);
            E[idx] = cur;
            L[idx++] = depth;
        }
    }

    vector <int> tree; int l;

    int query(int node, int x, int y, int s, int e)
    {
        if (x > e || y < s) return 0;

        if (s >= x && e <= y)
            return tree[node];

        int middle = (s + e) / 2;

        int id1 = query(node * 2, x, y, s, middle),
            id2 = query(node * 2 + 1, x, y, middle + 1, e);

        return (L[id1] > L[id2] ? id2 : id1);
    }

    int query(int i, int j) { return query(1, i, j, 1, l); }

    void Segment_tree(int n)
    {
        for (l = 1; l < n; l = (l << 1));
        tree.assign(2 * l, 0); L[0] = Inf;

        for (int i = 0; i < n; i++)
            tree[i + l] = i + 1;

        for (int i = l - 1; i > 0; i--)
        {
            tree[i] = (L[tree[2 * i]] > L[tree[2 * i + 1]] ?
                tree[2 * i + 1] : tree[2 * i]);
        }
    }

    int Ancestor(int i, int j)
    {
        int a = min(H[i], H[j]), b = max(H[i], H[j]);
        return E[query(a, b)];
    }

    int Dist(int x)
    {
        return L[H[x]];
    }

    int sol(int i, int j)
    {
        int g = Ancestor(i, j);
        return (Dist(i) + Dist(j) - (2 * Dist(g)));
    }

    LowerCommonAncestor(int lenght, int x)
    {
        n = lenght; idx = 1;

        L.assign(2 * n, -1);
        E.assign(2 * n, -1);
        H.assign(2 * n, -1);

        dfs(x, 0, 0); Segment_tree(2*n-2); //RMQ();
    }
};

struct DSU
{
    vector <int> link, size, mx;

    int find(int x)
    {
        while (x != link[x]) x = link[x];
        return x;
    }

    void unite(int a, int b)
    {
        a = find(a); b = find(b);
        if(a == b) return;
        if(size[a] < size[b]) swap(a, b);
        mx[a] = max(mx[a], mx[b]); 
        size[a] += size[b];
        link[b] = a;
    }

    DSU(int n)
    {
        mx.assign(n+1, 0); 
        link.assign(n+1, 0);
        size.assign(n+1, 1);
        _for(i, n+1) link[i] = mx[i] = i;
    }
};

void solve()
{
    int n, ans = 0; cin >> n; 
    vector <int> s(n+1), dp(n+1); 
    _for(i, n) cin >> s[i+1]; 
    v.assign(n+1, vector <int> ());
    vector <pair<int, int>> in;  
    _for(i, n-1)
    {
        int a, b; cin >> a >> b; 
        a = s[a]; b = s[b]; 
        if(a < b) swap(a, b);  
        v[a].push_back(b); 
        v[b].push_back(a); 
        in.push_back({a, b}); 
    }

    LowerCommonAncestor D(n, n); 
    sort(all(in)); DSU St(n); 

    for(auto& u : in)
    {
        int a = u.fs, b = u.sd; 
        a = St.find(a); b = St.find(b); 
        if(a == b) continue; 
        a = St.mx[a]; b = St.mx[b]; 
        St.unite(a, b); 
        if(St.mx[a] < St.mx[b]) swap(a, b);
        dp[a] = max(dp[a], dp[b] + D.sol(a, b)); 
        ans = max(ans, dp[a]); 
    }

    cout << ans << endl; 
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    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