Submission #766776

#	Time	Username	Problem	Language	Result	Execution time	Memory
766776		raysh07	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	295 ms	73544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct Tree {
	vector<vector<int>> adj, lift;	
	vector<int> d, tin, tout;
	int n, timer;
	bool initialized = false;
	bool dfsed = false;

	void init(int nn){
		n = nn;
		adj.resize(n + 1);
		d.resize(n + 1);
		lift.resize(n + 1);
		tin.resize(n + 1);
		tout.resize(n + 1);
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 0; i <= n; i++) lift[i].resize(20, 0);
		initialized = true;
	}

	void addEdge(int u, int v){
		if (!initialized){
			cout << "STUPID INITIALIZE\n";
			exit(0);
		}
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void build(){
		for (int j = 1; j < 20; j++){
			for (int i = 1; i <= n; i++){
				lift[i][j] = lift[lift[i][j - 1]][j - 1];
			}
		}
	}

	void dfs(int u, int par){
		tin[u] = ++timer;
		for (int v : adj[u]){
			if (v != par){
				d[v] = d[u] + 1;
				lift[v][0] = u;
				dfs(v, u);
			}
		}
		tout[u] = timer;
	}

	void dfs(int root = 1){
		if (!initialized){
			cout << "STUPID INITIALIZE\n";
			exit(0);
		}
		d[root] = 0;
		timer = 0;
		dfs(root, -1);
		build();
		dfsed = true;
	}

	int lca(int a, int b){
		if (!dfsed){
			cout << "STUPID DFS\n";
			exit(0);
		}
		if (d[a] < d[b]) swap(a, b);
		int del = d[a] - d[b];
		for (int i = 0; i < 20; i++) if (del >> i & 1) a = lift[a][i];

		if (a == b) return a;

		for (int i = 19; i >= 0; i--) if (lift[a][i] != lift[b][i]){
			a = lift[a][i];
			b = lift[b][i];
		}
		return lift[a][0];
	}

	int dist(int a, int b){
		return d[a] + d[b] - 2 * d[lca(a, b)];
	}
};

struct ufds{
	vector <int> root, sz, mx;
	int n;

	void init(int nn){
		n = nn;
		root.resize(n + 1);
		sz.resize(n + 1, 1);
		mx.resize(n + 1);
		for (int i = 1; i <= n; i++) root[i] = i, mx[i] = i;
	}

	int find(int x){
		if (root[x] == x) return x;
		return root[x] = find(root[x]);
	}

	bool unite(int x, int y){
		x = find(x); y = find(y);
		if (x == y) return false;

		if (sz[y] > sz[x]) swap(x, y);
		sz[x] += sz[y];
		root[y] = x;
		mx[x] = max(mx[x], mx[y]);
		return true;
	}
};

void Solve(){
	int n; cin >> n;
	vector <int> p(n + 1);
	for (int i = 1; i <= n; i++) cin >> p[i];

	Tree G;
	G.init(n);

	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		G.addEdge(p[u], p[v]);
	}
	G.dfs();

	vector <int> dp(n + 1, 0);
	ufds uf;
	uf.init(n);
	for (int i = 2; i <= n; i++){
		for (int v : G.adj[i]){
			if (v < i){
				int u = uf.mx[uf.find(v)];
				dp[i] = max(dp[i], dp[u] + G.dist(u, i));
				uf.unite(v, i);
			}
		}
	}

	cout << dp[n] << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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