oj.uz

Submission #827873

# Submission time Handle Problem Language Result Execution time Memory
827873 2023-08-16T21:12:55 Z CSQ31 Cat Exercise (JOI23_ho_t4) C++17
21 / 100
 2000 ms 35428 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];
vector<pii>g[MAXN];
int p[MAXN],rp[MAXN],t[4*MAXN],lazy[4*MAXN];
void pushdown(int v){
	if(!lazy[v])return;
	t[2*v] = lazy[2*v] = t[2*v+1] = lazy[2*v+1] = lazy[v];
	lazy[v] = 0;
}
void upd(int v,int l,int r,int tl,int tr,int val){
	if(l>r)return;
	if(l==tl && r==tr){
		t[v] = lazy[v] = val;
		return;
	}
	pushdown(v);
	int tm = (tl+tr)/2;
	upd(2*v,l,min(r,tm),tl,tm,val);
	upd(2*v+1,max(l,tm+1),r,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];
	pushdown(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 dep[MAXN],par[MAXN],ded[MAXN];
void dfs(int v){
	for(int x:adj[v]){
		if(x != par[v]){
			par[x] = v;
			dep[x] = dep[v]+1;
			dfs(x);
		}
	}
}
int dfs2(int v){
	int mx = 0;
	for(pii x:g[v]){
		mx = max(mx,dfs2(x.fi)+x.se);
	}
	return mx;
}

int find(int v,int u){
	int res = p[v];
	for(int x:adj[v]){
		if(x==u || ded[x])continue;
		res = max(res,find(x,v));
	}
	return res;
}
void solve(int v,int p){
	v = rp[find(v,-1)];
	ded[v] = 1;
	if(p)g[p].pb({v,abs(dep[v]-dep[p])});
	for(int x:adj[v]){
		if(ded[x])continue;
		solve(x,v);
	}
}

int main()
{
	owo
	int n;
	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]);
	solve(1,0);
	cout<<dfs2(rp[n]);
	
	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 4 ms 9724 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9724 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 84 ms 10504 KB Output is correct
19 Correct 90 ms 10412 KB Output is correct
20 Correct 78 ms 10404 KB Output is correct
21 Correct 6 ms 10372 KB Output is correct
22 Correct 8 ms 10468 KB Output is correct
23 Correct 6 ms 10452 KB Output is correct
24 Correct 7 ms 10376 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 4 ms 9724 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9724 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 84 ms 10504 KB Output is correct
19 Correct 90 ms 10412 KB Output is correct
20 Correct 78 ms 10404 KB Output is correct
21 Correct 6 ms 10372 KB Output is correct
22 Correct 8 ms 10468 KB Output is correct
23 Correct 6 ms 10452 KB Output is correct
24 Correct 7 ms 10376 KB Output is correct
25 Correct 4 ms 9716 KB Output is correct
26 Correct 91 ms 10540 KB Output is correct
27 Correct 86 ms 10316 KB Output is correct
28 Correct 95 ms 10316 KB Output is correct
29 Correct 86 ms 10320 KB Output is correct
30 Incorrect 10 ms 10068 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 4 ms 9724 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9724 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 84 ms 10504 KB Output is correct
19 Correct 90 ms 10412 KB Output is correct
20 Correct 78 ms 10404 KB Output is correct
21 Correct 6 ms 10372 KB Output is correct
22 Correct 8 ms 10468 KB Output is correct
23 Correct 6 ms 10452 KB Output is correct
24 Correct 7 ms 10376 KB Output is correct
25 Execution timed out 2075 ms 35428 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 4 ms 9684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 4 ms 9724 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9724 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 84 ms 10504 KB Output is correct
19 Correct 90 ms 10412 KB Output is correct
20 Correct 78 ms 10404 KB Output is correct
21 Correct 6 ms 10372 KB Output is correct
22 Correct 8 ms 10468 KB Output is correct
23 Correct 6 ms 10452 KB Output is correct
24 Correct 7 ms 10376 KB Output is correct
25 Correct 4 ms 9716 KB Output is correct
26 Correct 91 ms 10540 KB Output is correct
27 Correct 86 ms 10316 KB Output is correct
28 Correct 95 ms 10316 KB Output is correct
29 Correct 86 ms 10320 KB Output is correct
30 Incorrect 10 ms 10068 KB Output isn't correct
31 Halted 0 ms 0 KB -