Submission #937463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937463	2024-03-04T06:00:49 Z	william950615	Cat Exercise (JOI23_ho_t4)	C++14	21 / 100	128 ms	51124 KB

Main


#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mkp make_pair
#define MEM(x) memset(x,0,sizeof(x))
#define ALL(x) begin(x), end(x)
#define PH push
#define PB push_back
#define REP(i,N) for( int i = 0; i <(N); ++i )
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i )

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
template<typename T>
using V = vector<T>;

#ifdef LOCAL
int __lg( int x ) {
	return 31 - __builtin_clz( x );
}
#endif
struct DSU {
	const int N;
	V<int> fth;

	int find( int a ) { return a == fth[a] ? a : fth[a] = find(fth[a]);};
	int merge( int a, int b ) { // make a be father
		const int fa = find( a ), fb = find( b );
		if( fa == fb ) return 0;
		fth[ fb ] = fa;
		return 1;
	}
	DSU( int N ) : N(N) {
		fth.assign( N+1, 0 );
		iota( ALL(fth), 0 );
	}
};

struct LCA {
	const int N;
	int lgN, tm;
	V<int> dis;
	V<int> tin, tout;

	V<V<int>> fth;

	V<V<int>> G;


	void dfs( int cur, int par ) {
		tin[cur]=++tm;
		for( int i = 1; i < lgN; ++i ) 
			fth[ i ][ cur ] = fth[ i-1 ][ fth[i-1][cur] ];

		for( auto &i : G[cur] ) {
			if( i == par ) continue;
			fth[ 0 ][ i ] = cur;
			dis[ i ] = dis[ cur ] + 1;
			dfs( i, cur );
		}	
		tout[cur]=++tm;
	}

	bool isfather( int a, int b ) { 
		return tin[a] <= tin[b] && tout[b] <= tout[a];
	}

	int lca( int a, int b ) {
		if( isfather(a,b) ) return a;
		if( isfather(b,a) ) return b;
		for( int i = lgN-1; i >= 0; --i ) {
			if( !isfather( fth[ i ][ a ], b ) )
				a = fth[ i ][ a];
		}	
		return fth[ 0 ][ a ];
	}


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



	LCA( V<V<int>>&_G, int N ) : N(N) {
		tm = 0;
		lgN = __lg( N ) + 1;
		tin.assign( N+1, 0 );
		tout.assign( N+1, 0 );
		fth.assign( lgN, V<int>(N+1,0));
		dis.assign( N+1, 0 );

		G=_G;
		dfs( 1, 0 );
		V<V<int>>().swap( G );
	}	
};

void solve() {
	int N; cin >> N;
	V<int> NodeOf(N+1,0);
	FOR(i,1,N) {
		int p; cin >> p;
		NodeOf[ p ] = i;
	}

	V<V<int>> G(N+1);

	FOR(i,2,N) {
		int a, b; cin >> a >> b;
		G[a].PB( b );
		G[b].PB( a );
	}

	LCA lca(G, N);
	DSU dsu(N+1);

	V<int> vis(N+1,0);
	V<int> dp(N+1,0);

	FOR(_,1,N) {
		auto nd = NodeOf[_];


		for( auto&j : G[nd] ) {
			if( !vis[j] ) continue;
			auto to  = dsu.find( j );
			dp[ nd ] = max( dp[ nd ], lca.Dis(nd,to) + dp[ to ] );
			dsu.merge( nd, j );
		}

		vis[ nd ] = true;
	}
	cout << *max_element( ALL(dp) ) << '\n';
}

int main () {
	int T=1;
#ifdef LOCAL
	freopen( "input.txt", "r", stdin );
	freopen( "output.txt", "w", stdout );
	cin >> T;
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
	while(T--) solve();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	460 KB	Output is correct
13	Correct	1 ms	452 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	460 KB	Output is correct
13	Correct	1 ms	452 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1488 KB	Output is correct
20	Correct	2 ms	1368 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	3 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1372 KB	Output is correct

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	460 KB	Output is correct
13	Correct	1 ms	452 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1488 KB	Output is correct
20	Correct	2 ms	1368 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	3 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1372 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	3 ms	1372 KB	Output is correct
27	Incorrect	2 ms	1372 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	460 KB	Output is correct
13	Correct	1 ms	452 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1488 KB	Output is correct
20	Correct	2 ms	1368 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	3 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1372 KB	Output is correct
25	Incorrect	128 ms	51124 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	460 KB	Output is correct
13	Correct	1 ms	452 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1488 KB	Output is correct
20	Correct	2 ms	1368 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	3 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1372 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	3 ms	1372 KB	Output is correct
27	Incorrect	2 ms	1372 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Submission #937463

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0