답안 #758883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758883	2023-06-15T12:14:01 Z	PoPularPlusPlus	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	294 ms	50228 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

const int N = 200003 , L = 20;

struct dsu {
	vector<int> p , siz , mn;
	
	void init(vector<int> a){
		int n = a.size();
		p.resize(n);
		siz.resize(n);
		mn.resize(n);
		for(int i = 0; i < n; i++){
			p[i] = i;
			siz[i] = 1;
			mn[i] = a[i];
		}
	}
	
	int get(int x){
		return p[x] = (p[x] == x ? x : get(p[x]));
	}
	
	void unio(int x , int y){
		x = get(x);
		y = get(y);
		if(x == y)return;
		if(siz[x] > siz[y]){
			swap(x,y);
		}
		p[x] = y;
		siz[y] += siz[x];
		mn[y] = max(mn[y],mn[x]);
	}
};

vector<int> adj[N];

int timer,tin[N],tout[N],up[N][L],depth[N];

void dfs(int node , int par){
	tin[node] = timer++;
	up[node][0] = par;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
	}
	for(int i : adj[node]){
		if(i!=par){
			depth[i] = depth[node] + 1;
			dfs(i,node);
		}
	}
	tout[node] = timer++;
}

bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L-1; i >= 0; i--){
		if(!is_lca(up[x][i],y))x = up[x][i];
	}
	return up[x][0];
}

int dis(int u , int v){
	int lca = find(u , v);
	return depth[u] + depth[v] - 2 * depth[lca];
}

void solve(){
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	arr[0] = 0;
	int pos[n + 1];
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
		pos[arr[i]] = i;
	}
	for(int i = 0; i < n - 1; i++){
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	timer = 0;
	depth[1] = 0;
	dfs(1,1);
	
	dsu d;
	d.init(arr);
	ll ans[n + 1];
	ans[1] = 0;
	for(int i = 2; i <= n; i++){
		ans[i] = 0;
		int node = pos[i];
		for(int j : adj[node]){
			if(arr[j] < i){
				//cout << dis(node , pos[d.mn[d.get(j)]]) << ' ' << pos[d.mn[d.get(j)]] << ' ';
				//cout << dis(node,d.mn[d.get(j)]) << ' ' << d.mn[d.get(j)] << ' ';
				ans[i] = max(ans[i] , dis(node,pos[d.mn[d.get(j)]]) + ans[d.mn[d.get(j)]]);
				d.unio(j , node);
			}
		}
		//cout << ans[i] << ' ';
	}
	cout << ans[n] << '\n';
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("deleg.in", "r", stdin);
//freopen("deleg.out", "w", stdout);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5028 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 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	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5024 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5028 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 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	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5024 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	5076 KB	Output is correct
13	Correct	3 ms	5076 KB	Output is correct
14	Correct	3 ms	5028 KB	Output is correct
15	Correct	2 ms	5076 KB	Output is correct
16	Correct	3 ms	5028 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5028 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 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	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5024 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	5076 KB	Output is correct
13	Correct	3 ms	5076 KB	Output is correct
14	Correct	3 ms	5028 KB	Output is correct
15	Correct	2 ms	5076 KB	Output is correct
16	Correct	3 ms	5028 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	4 ms	6100 KB	Output is correct
19	Correct	5 ms	6100 KB	Output is correct
20	Correct	4 ms	6064 KB	Output is correct
21	Correct	4 ms	6064 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct
23	Correct	5 ms	6028 KB	Output is correct
24	Correct	4 ms	6100 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5028 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 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	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5024 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	5076 KB	Output is correct
13	Correct	3 ms	5076 KB	Output is correct
14	Correct	3 ms	5028 KB	Output is correct
15	Correct	2 ms	5076 KB	Output is correct
16	Correct	3 ms	5028 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	4 ms	6100 KB	Output is correct
19	Correct	5 ms	6100 KB	Output is correct
20	Correct	4 ms	6064 KB	Output is correct
21	Correct	4 ms	6064 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct
23	Correct	5 ms	6028 KB	Output is correct
24	Correct	4 ms	6100 KB	Output is correct
25	Correct	3 ms	5028 KB	Output is correct
26	Correct	5 ms	5972 KB	Output is correct
27	Correct	5 ms	5936 KB	Output is correct
28	Correct	6 ms	5936 KB	Output is correct
29	Correct	6 ms	6060 KB	Output is correct
30	Correct	8 ms	5812 KB	Output is correct
31	Correct	6 ms	5844 KB	Output is correct
32	Correct	6 ms	5804 KB	Output is correct
33	Correct	5 ms	5844 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5028 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 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	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5024 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	5076 KB	Output is correct
13	Correct	3 ms	5076 KB	Output is correct
14	Correct	3 ms	5028 KB	Output is correct
15	Correct	2 ms	5076 KB	Output is correct
16	Correct	3 ms	5028 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	4 ms	6100 KB	Output is correct
19	Correct	5 ms	6100 KB	Output is correct
20	Correct	4 ms	6064 KB	Output is correct
21	Correct	4 ms	6064 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct
23	Correct	5 ms	6028 KB	Output is correct
24	Correct	4 ms	6100 KB	Output is correct
25	Correct	86 ms	50092 KB	Output is correct
26	Correct	99 ms	50228 KB	Output is correct
27	Correct	89 ms	50220 KB	Output is correct
28	Correct	123 ms	50176 KB	Output is correct
29	Correct	125 ms	49948 KB	Output is correct
30	Correct	117 ms	50148 KB	Output is correct
31	Correct	128 ms	50224 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	129 ms	38304 KB	Output is correct
4	Correct	128 ms	38304 KB	Output is correct
5	Correct	163 ms	38312 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5028 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 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	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5024 KB	Output is correct
11	Correct	3 ms	5024 KB	Output is correct
12	Correct	3 ms	5076 KB	Output is correct
13	Correct	3 ms	5076 KB	Output is correct
14	Correct	3 ms	5028 KB	Output is correct
15	Correct	2 ms	5076 KB	Output is correct
16	Correct	3 ms	5028 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	4 ms	6100 KB	Output is correct
19	Correct	5 ms	6100 KB	Output is correct
20	Correct	4 ms	6064 KB	Output is correct
21	Correct	4 ms	6064 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct
23	Correct	5 ms	6028 KB	Output is correct
24	Correct	4 ms	6100 KB	Output is correct
25	Correct	3 ms	5028 KB	Output is correct
26	Correct	5 ms	5972 KB	Output is correct
27	Correct	5 ms	5936 KB	Output is correct
28	Correct	6 ms	5936 KB	Output is correct
29	Correct	6 ms	6060 KB	Output is correct
30	Correct	8 ms	5812 KB	Output is correct
31	Correct	6 ms	5844 KB	Output is correct
32	Correct	6 ms	5804 KB	Output is correct
33	Correct	5 ms	5844 KB	Output is correct
34	Correct	86 ms	50092 KB	Output is correct
35	Correct	99 ms	50228 KB	Output is correct
36	Correct	89 ms	50220 KB	Output is correct
37	Correct	123 ms	50176 KB	Output is correct
38	Correct	125 ms	49948 KB	Output is correct
39	Correct	117 ms	50148 KB	Output is correct
40	Correct	128 ms	50224 KB	Output is correct
41	Correct	3 ms	4948 KB	Output is correct
42	Correct	3 ms	5076 KB	Output is correct
43	Correct	129 ms	38304 KB	Output is correct
44	Correct	128 ms	38304 KB	Output is correct
45	Correct	163 ms	38312 KB	Output is correct
46	Correct	231 ms	44608 KB	Output is correct
47	Correct	231 ms	43568 KB	Output is correct
48	Correct	294 ms	45260 KB	Output is correct
49	Correct	235 ms	43536 KB	Output is correct
50	Correct	206 ms	38524 KB	Output is correct
51	Correct	241 ms	38732 KB	Output is correct
52	Correct	225 ms	38640 KB	Output is correct
53	Correct	204 ms	38636 KB	Output is correct

답안 #758883

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

Subtask #6 23.0 / 23.0

Subtask #7 26.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
20.0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
26.0 / 26.0