Submission #789102

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789102	2023-07-21T04:48:21 Z	ono_de206	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	2000 ms	29076 KB

Main

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<int, int> P;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
	return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
	return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
	return in;
}

template<typename T, typename U>
	istream & operator >> (istream &in, pair<T, U> &c) {
	in >> c.first;
	in >> c.second;
	return in;
}

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, inf = 1e18 + 10;
int p[mxn], vis[mxn];
vector<int> g[mxn];
pair<int, int> mx;

void dfs(int to, int fr, int dp = 1) {
	if(p[mx.ff] < p[to]) mx = {to, dp};
	for(int x : g[to]) {
		if(vis[x] || x == fr) continue;
		dfs(x, to, dp + 1);
	}
}

int solve(int n) {
	vis[n] = 1;
	int ret = 0;
	for(int x : g[n]) {
		if(vis[x]) continue;
		mx = {0, 0};
		dfs(x, n);
		mxx(ret, mx.ss + solve(mx.ff));
	}
	return ret;
}

void go() {
	int n, root = 0;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
		if(p[i] == n) root = i;
	}
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	cout << solve(root) << '\n';
}

signed main() {
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	5024 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	2 ms	5024 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	4948 KB	Output is correct
18	Correct	86 ms	5608 KB	Output is correct
19	Correct	84 ms	5588 KB	Output is correct
20	Correct	75 ms	5604 KB	Output is correct
21	Correct	4 ms	5556 KB	Output is correct
22	Correct	4 ms	5460 KB	Output is correct
23	Correct	4 ms	5460 KB	Output is correct
24	Correct	4 ms	5460 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	5024 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	2 ms	5024 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	4948 KB	Output is correct
18	Correct	86 ms	5608 KB	Output is correct
19	Correct	84 ms	5588 KB	Output is correct
20	Correct	75 ms	5604 KB	Output is correct
21	Correct	4 ms	5556 KB	Output is correct
22	Correct	4 ms	5460 KB	Output is correct
23	Correct	4 ms	5460 KB	Output is correct
24	Correct	4 ms	5460 KB	Output is correct
25	Correct	2 ms	4948 KB	Output is correct
26	Correct	95 ms	5548 KB	Output is correct
27	Correct	89 ms	5564 KB	Output is correct
28	Correct	84 ms	5588 KB	Output is correct
29	Correct	92 ms	5588 KB	Output is correct
30	Correct	10 ms	5368 KB	Output is correct
31	Correct	13 ms	5368 KB	Output is correct
32	Correct	10 ms	5376 KB	Output is correct
33	Correct	12 ms	5296 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	5024 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	2 ms	5024 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	4948 KB	Output is correct
18	Correct	86 ms	5608 KB	Output is correct
19	Correct	84 ms	5588 KB	Output is correct
20	Correct	75 ms	5604 KB	Output is correct
21	Correct	4 ms	5556 KB	Output is correct
22	Correct	4 ms	5460 KB	Output is correct
23	Correct	4 ms	5460 KB	Output is correct
24	Correct	4 ms	5460 KB	Output is correct
25	Execution timed out	2086 ms	29076 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Execution timed out	2054 ms	19712 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	5024 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	2 ms	5024 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	4948 KB	Output is correct
18	Correct	86 ms	5608 KB	Output is correct
19	Correct	84 ms	5588 KB	Output is correct
20	Correct	75 ms	5604 KB	Output is correct
21	Correct	4 ms	5556 KB	Output is correct
22	Correct	4 ms	5460 KB	Output is correct
23	Correct	4 ms	5460 KB	Output is correct
24	Correct	4 ms	5460 KB	Output is correct
25	Correct	2 ms	4948 KB	Output is correct
26	Correct	95 ms	5548 KB	Output is correct
27	Correct	89 ms	5564 KB	Output is correct
28	Correct	84 ms	5588 KB	Output is correct
29	Correct	92 ms	5588 KB	Output is correct
30	Correct	10 ms	5368 KB	Output is correct
31	Correct	13 ms	5368 KB	Output is correct
32	Correct	10 ms	5376 KB	Output is correct
33	Correct	12 ms	5296 KB	Output is correct
34	Execution timed out	2086 ms	29076 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Submission #789102

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.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
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0