Submission #920445

#	Time	Username	Problem	Language	Result	Execution time	Memory
920445		Ludissey	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	804 ms	148176 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> adj;
int n; 
const int LOG=63;
vector<int> p;
vector<int> depth;
vector<bool> proc;
vector<bool> visited;
vector<int> parent;
vector<vector<pair<int,int>>> child;
vector<vector<int>> ancestors;
vector<int> sz;

int lca(int a, int b){
    if(depth[b]>depth[a]) swap(a,b);
    int k=depth[a]-depth[b];
    for (int j = LOG-1; j >= 0; j--)
    {
        if(k&((long long)1<<j)) a=ancestors[a][j];
    }
    if(a==b) return a;
    for (int j = LOG-1; j >= 0; j--)
    {
        if(ancestors[a][j]!=ancestors[b][j]) {
            a=ancestors[a][j];
            b=ancestors[b][j];
        }
    }
    return ancestors[a][0];
}

void setup_ancestors(){
    for (int k = 1; k < LOG; k++)
    {
        for (int i = 0; i < n; i++)
        {
            ancestors[i][k]=ancestors[ancestors[i][k-1]][k-1];
        }
    }
}

int getParent(int a) {
    if(a==parent[a]) return a;
    return parent[a]=getParent(parent[a]);
}

void unify(int a, int b){
    a=getParent(a);
    b=getParent(b);
    if(a==b) return;
    int lc=lca(a,b);
    int dist=(depth[a]+depth[b])-(2*depth[lc]);
    parent[b]=a;
    child[a].push_back({b,dist});
    sz[a]+=sz[b];
}

void reconstructTree(){
    vector<pair<int,int>> _p;
    for (int i = 0; i < n; i++) _p.push_back({p[i], i});
    sort(_p.begin(), _p.end());
    for (int i = 0; i < n; i++)
    {
        for (auto u : adj[_p[i].second])
        {
            if(proc[u]) unify(_p[i].second, getParent(u));
        }
        proc[_p[i].second]=true;
    }
}

void smltree(int i, int dpth){
    if(visited[i]) return;
    visited[i]=true;
    depth[i]=dpth;
    for (auto u : adj[i]) {
        if(visited[u]) continue;
        ancestors[u][0]=i;
        smltree(u, depth[i]+1);
    }
}

int dfs(int i){
    int sum=0;
    if(visited[i]) return 0;
    visited[i]=true;
    if(child[i].size()==0) return 0;
    for (auto u : child[i]) {
        sum=max(sum, dfs(u.first)+u.second);
    }
    return sum;
}

signed main() {
	// Input:
    cin >> n;

    p.resize(n);
    visited.resize(n, false);
    parent.resize(n);
    child.resize(n);
    proc.resize(n);
    depth.resize(n);
    sz.resize(n, 1);
    adj.resize(n);

    int start;
    for (int i = 0; i < n; i++){
        cin >> p[i];
        if (p[i] == n) start = i;
        parent[i]=i;
    }
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }


    ancestors.resize(n, vector<int>(LOG, start));
    smltree(start,0);
    setup_ancestors();
    reconstructTree();
    visited.clear();
    visited.resize(n, false);
    cout << dfs(start) << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:131:22: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |     cout << dfs(start) << "\n";
      |                      ^

• 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