oj.uz

Submission #766764

# Submission time Handle Problem Language Result Execution time Memory
766764 2023-06-26T07:09:18 Z raysh07 Cat Exercise (JOI23_ho_t4) C++17
7 / 100
 2000 ms 62832 KB 
#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;
	int n;

	void init(int nn){
		n = nn;
		root.resize(n + 1);
		sz.resize(n + 1, 1);
		for (int i = 1; i <= n; i++) root[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;
		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){
				uf.unite(v, i);
			}
		}

		pair <int, int> mx = {-1, -1};
		for (int j = 1; j < i; j++){
			if (uf.find(j) == uf.find(i)){
				mx = max(mx, {dp[j], j});
			}
		}

		for (int j = 1; j < i; j++){
			if (uf.find(j) == uf.find(i) && j == mx.second){
				dp[i] = max(dp[i], dp[j] + G.dist(i, j));
			}
		}
	}

	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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Execution timed out 2072 ms 62832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -