| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 797865 |
2023-07-30T04:03:22 Z |
1bin |
Cat Exercise (JOI23_ho_t4) |
C++14 |
|
210 ms |
61852 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
ll n, h[NMAX], a, b, lv[NMAX], p[NMAX][18], par[NMAX], dp[NMAX];
vector<int> adj[NMAX];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}
void dfs(int x, int par){
for(int& nx : adj[x]){
if(nx == par) continue;
p[nx][0] = x;
lv[nx] = lv[x] + 1;
dfs(nx, x);
}
return;
}
int dist(int a, int b){
int ret = 0;
if(lv[a] < lv[b]) swap(a, b);
for(int i = 17; i >= 0; i--)
if(lv[a] - lv[b] >= 1 << i){
a = p[a][i];
ret += 1 << i;
}
if(a == b) return ret;
for(int i = 17; i >= 0; i--)
if(p[a][i] != p[b][i]){
a = p[a][i];
b = p[b][i];
ret += 1 << (i + 1);
}
return ret + 2;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i < n; i++){
cin >> a >> b;
adj[h[a]].emplace_back(h[b]);
adj[h[b]].emplace_back(h[a]);
}
dfs(1, -1);
for(int j = 1; j < 18; j++)
for(int i = 1; i <= n; i++)
p[i][j] = p[p[i][j - 1]][j - 1];
memset(par, -1, sizeof(par));
for(int i = 1; i <= n; i++){
for(int j : adj[i]){
j = find(j);
if(j > i) continue;
dp[i] = max(dp[i], dp[j] + dist(i, j));
par[j] = i;
}
}
cout << dp[n];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 17 |
Correct |
3 ms |
6688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 17 |
Correct |
3 ms |
6688 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7892 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 17 |
Correct |
3 ms |
6688 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7892 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 25 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 26 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 27 |
Correct |
5 ms |
7792 KB |
Output is correct |
| 28 |
Correct |
6 ms |
7812 KB |
Output is correct |
| 29 |
Correct |
7 ms |
7784 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 31 |
Correct |
5 ms |
7600 KB |
Output is correct |
| 32 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 33 |
Correct |
5 ms |
7544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 17 |
Correct |
3 ms |
6688 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7892 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 25 |
Correct |
124 ms |
55756 KB |
Output is correct |
| 26 |
Correct |
124 ms |
61836 KB |
Output is correct |
| 27 |
Correct |
138 ms |
61852 KB |
Output is correct |
| 28 |
Correct |
174 ms |
61320 KB |
Output is correct |
| 29 |
Correct |
206 ms |
55776 KB |
Output is correct |
| 30 |
Correct |
181 ms |
59796 KB |
Output is correct |
| 31 |
Correct |
171 ms |
58640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
210 ms |
49280 KB |
Output is correct |
| 4 |
Correct |
167 ms |
49356 KB |
Output is correct |
| 5 |
Correct |
183 ms |
49380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6564 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 17 |
Correct |
3 ms |
6688 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7892 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7800 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7856 KB |
Output is correct |
| 25 |
Correct |
3 ms |
6568 KB |
Output is correct |
| 26 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 27 |
Correct |
5 ms |
7792 KB |
Output is correct |
| 28 |
Correct |
6 ms |
7812 KB |
Output is correct |
| 29 |
Correct |
7 ms |
7784 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 31 |
Correct |
5 ms |
7600 KB |
Output is correct |
| 32 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 33 |
Correct |
5 ms |
7544 KB |
Output is correct |
| 34 |
Correct |
124 ms |
55756 KB |
Output is correct |
| 35 |
Correct |
124 ms |
61836 KB |
Output is correct |
| 36 |
Correct |
138 ms |
61852 KB |
Output is correct |
| 37 |
Correct |
174 ms |
61320 KB |
Output is correct |
| 38 |
Correct |
206 ms |
55776 KB |
Output is correct |
| 39 |
Correct |
181 ms |
59796 KB |
Output is correct |
| 40 |
Correct |
171 ms |
58640 KB |
Output is correct |
| 41 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 42 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 43 |
Correct |
210 ms |
49280 KB |
Output is correct |
| 44 |
Correct |
167 ms |
49356 KB |
Output is correct |
| 45 |
Correct |
183 ms |
49380 KB |
Output is correct |
| 46 |
Correct |
166 ms |
58188 KB |
Output is correct |
| 47 |
Correct |
150 ms |
58180 KB |
Output is correct |
| 48 |
Correct |
145 ms |
58212 KB |
Output is correct |
| 49 |
Correct |
140 ms |
58252 KB |
Output is correct |
| 50 |
Correct |
186 ms |
49508 KB |
Output is correct |
| 51 |
Correct |
186 ms |
49484 KB |
Output is correct |
| 52 |
Correct |
193 ms |
49748 KB |
Output is correct |
| 53 |
Correct |
193 ms |
49572 KB |
Output is correct |
