oj.uz

Submission #827890

# Submission time Handle Problem Language Result Execution time Memory
827890 2023-08-16T21:42:48 Z CSQ31 Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 195 ms 62612 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -