Submission #937466

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937466	2024-03-04T06:12:29 Z	william950615	Cat Exercise (JOI23_ho_t4)	C++14	41 / 100	139 ms	47428 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<ll> 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 ], dp[ to ] + lca.Dis(nd,to));
			dsu.merge( nd, j );
		}

		vis[ nd ] = true;
	}
	cout << dp[ NodeOf[N] ] << '\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	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	388 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	344 KB	Output is correct
9	Correct	344 KB	Output is correct
10	Correct	348 KB	Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	388 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	2 ms	1372 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	388 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	2 ms	1372 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 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	0 ms	348 KB	Output is correct
26	Correct	3 ms	1372 KB	Output is correct
27	Incorrect	3 ms	1372 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	388 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	2 ms	1372 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 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	110 ms	47428 KB	Output is correct
26	Correct	118 ms	47268 KB	Output is correct
27	Correct	112 ms	47372 KB	Output is correct
28	Correct	135 ms	47424 KB	Output is correct
29	Correct	135 ms	47428 KB	Output is correct
30	Correct	139 ms	47292 KB	Output is correct
31	Correct	129 ms	47424 KB	Output is correct

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	388 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1372 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	2 ms	1372 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 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	0 ms	348 KB	Output is correct
26	Correct	3 ms	1372 KB	Output is correct
27	Incorrect	3 ms	1372 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Submission #937466

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 20.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
20.0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0