답안 #827890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827890	2023-08-16T21:42:48 Z	CSQ31	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	195 ms	62612 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5;
vector<int>adj[MAXN],g[MAXN];
int p[MAXN],rp[MAXN],n;
int tin[MAXN],tout[MAXN],dep[MAXN],par[20][MAXN];
int timer = 0;
void dfs(int v,int u){
	tin[v] = ++timer;
	for(int x:adj[v]){
	    if(x == u)continue;	
	    par[0][x] = v;
	    dep[x] = dep[v]+1;
	    for(int i=1;i<=18;i++){
			par[i][x] = par[i-1][par[i-1][x]];
		}
		dfs(x,v);
	}
	tout[v] = timer;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
	if(dep[v] > dep[u])swap(u,v);
	int dist = dep[u]-dep[v];
	for(int i=0;dist;i++,dist>>=1){
		if(dist&1)u = par[i][u];
	}
	if(u == v)return u;
	for(int i=18;i>=0;i--){
		if(par[i][v] != par[i][u]){
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}
int dist(int u,int v){
	int w = lca(u,v);
	return dep[u] + dep[v] - 2*dep[w];
}

////lca template
int t[4*MAXN];
void upd(int v,int pos,int tl,int tr,int val){
	if(tl==tr){
		t[v] = val;
		return;
	}
	int tm = (tl+tr)/2;
	if(pos<=tm)upd(2*v,pos,tl,tm,val);
	else upd(2*v+1,pos,tm+1,tr,val);
	t[v] = max(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
	if(l>r)return -1;
	if(l==tl && r==tr)return t[v];
	int tm = (tl+tr)/2;
	return max(
	query(2*v,l,min(r,tm),tl,tm),
	query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
int ded[MAXN];
int solve(int v){
	int rt = query(1,tin[v],tout[v],1,n);
	//cout<<v<<" "<<rt<<'\n';
	rt = rp[rt];
	ded[rt] = 1;
	upd(1,tin[rt],1,n,-1);
	for(int x:adj[rt]){
		if(x == par[0][rt] || ded[x])continue;
		int y = solve(x);
		g[rt].pb(y);
	}
	if(rt != v){
		int y = solve(v);
		g[rt].pb(y);
	}
	return rt;
}
int dfs2(int v){
	int mx = 0;
	for(int x:g[v]){
		mx = max(mx,dfs2(x) + dist(x,v));
	}
	return mx;
}
//segtree
int main()
{
	owo
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		rp[p[i]] = i;
	}
	for(int i=1;i<n;i++){
		int v,u;
		cin>>v>>u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	dfs(rp[n],-1);
	for(int i=1;i<=n;i++)upd(1,tin[i],1,n,p[i]);
	
	solve(rp[n]);
	cout<<dfs2(rp[n]);
	
	
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	5 ms	9752 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9768 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	6 ms	9808 KB	Output is correct
9	Correct	4 ms	9812 KB	Output is correct
10	Correct	9 ms	9812 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	5 ms	9752 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9768 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	6 ms	9808 KB	Output is correct
9	Correct	4 ms	9812 KB	Output is correct
10	Correct	9 ms	9812 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	5 ms	9940 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	4 ms	9812 KB	Output is correct
16	Correct	5 ms	9932 KB	Output is correct
17	Correct	4 ms	9812 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	5 ms	9752 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9768 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	6 ms	9808 KB	Output is correct
9	Correct	4 ms	9812 KB	Output is correct
10	Correct	9 ms	9812 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	5 ms	9940 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	4 ms	9812 KB	Output is correct
16	Correct	5 ms	9932 KB	Output is correct
17	Correct	4 ms	9812 KB	Output is correct
18	Correct	8 ms	11092 KB	Output is correct
19	Correct	8 ms	11048 KB	Output is correct
20	Correct	8 ms	11092 KB	Output is correct
21	Correct	7 ms	10920 KB	Output is correct
22	Correct	8 ms	10836 KB	Output is correct
23	Correct	8 ms	10836 KB	Output is correct
24	Correct	8 ms	10836 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	5 ms	9752 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9768 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	6 ms	9808 KB	Output is correct
9	Correct	4 ms	9812 KB	Output is correct
10	Correct	9 ms	9812 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	5 ms	9940 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	4 ms	9812 KB	Output is correct
16	Correct	5 ms	9932 KB	Output is correct
17	Correct	4 ms	9812 KB	Output is correct
18	Correct	8 ms	11092 KB	Output is correct
19	Correct	8 ms	11048 KB	Output is correct
20	Correct	8 ms	11092 KB	Output is correct
21	Correct	7 ms	10920 KB	Output is correct
22	Correct	8 ms	10836 KB	Output is correct
23	Correct	8 ms	10836 KB	Output is correct
24	Correct	8 ms	10836 KB	Output is correct
25	Correct	4 ms	9812 KB	Output is correct
26	Correct	8 ms	10964 KB	Output is correct
27	Correct	8 ms	10964 KB	Output is correct
28	Correct	9 ms	10964 KB	Output is correct
29	Correct	8 ms	10964 KB	Output is correct
30	Correct	9 ms	10584 KB	Output is correct
31	Correct	8 ms	10592 KB	Output is correct
32	Correct	9 ms	10692 KB	Output is correct
33	Correct	8 ms	10636 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	5 ms	9752 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9768 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	6 ms	9808 KB	Output is correct
9	Correct	4 ms	9812 KB	Output is correct
10	Correct	9 ms	9812 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	5 ms	9940 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	4 ms	9812 KB	Output is correct
16	Correct	5 ms	9932 KB	Output is correct
17	Correct	4 ms	9812 KB	Output is correct
18	Correct	8 ms	11092 KB	Output is correct
19	Correct	8 ms	11048 KB	Output is correct
20	Correct	8 ms	11092 KB	Output is correct
21	Correct	7 ms	10920 KB	Output is correct
22	Correct	8 ms	10836 KB	Output is correct
23	Correct	8 ms	10836 KB	Output is correct
24	Correct	8 ms	10836 KB	Output is correct
25	Incorrect	168 ms	62612 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9812 KB	Output is correct
2	Correct	5 ms	9776 KB	Output is correct
3	Correct	192 ms	42920 KB	Output is correct
4	Correct	195 ms	46772 KB	Output is correct
5	Correct	184 ms	46464 KB	Output is correct

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	5 ms	9752 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9768 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	6 ms	9808 KB	Output is correct
9	Correct	4 ms	9812 KB	Output is correct
10	Correct	9 ms	9812 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	5 ms	9940 KB	Output is correct
14	Correct	5 ms	9812 KB	Output is correct
15	Correct	4 ms	9812 KB	Output is correct
16	Correct	5 ms	9932 KB	Output is correct
17	Correct	4 ms	9812 KB	Output is correct
18	Correct	8 ms	11092 KB	Output is correct
19	Correct	8 ms	11048 KB	Output is correct
20	Correct	8 ms	11092 KB	Output is correct
21	Correct	7 ms	10920 KB	Output is correct
22	Correct	8 ms	10836 KB	Output is correct
23	Correct	8 ms	10836 KB	Output is correct
24	Correct	8 ms	10836 KB	Output is correct
25	Correct	4 ms	9812 KB	Output is correct
26	Correct	8 ms	10964 KB	Output is correct
27	Correct	8 ms	10964 KB	Output is correct
28	Correct	9 ms	10964 KB	Output is correct
29	Correct	8 ms	10964 KB	Output is correct
30	Correct	9 ms	10584 KB	Output is correct
31	Correct	8 ms	10592 KB	Output is correct
32	Correct	9 ms	10692 KB	Output is correct
33	Correct	8 ms	10636 KB	Output is correct
34	Incorrect	168 ms	62612 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #827890

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 23.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
23.0 / 23.0

Subtask #7
0 / 26.0