Submission #1155307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155307		dnnnda	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	2095 ms	17592 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;

int p[200005];
ll ans[200005];
vector<int> adj[200005];

ll dfs(int mx, int node, int pre, int l){
    if(p[node]>mx) return 0;
    ll ret=l+ans[node];
    for(int i:adj[node]) if(i!=pre) ret=max(ret,dfs(mx,i,node,l+1));
    return ret;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for(int i=1 ; i<=n ; i++) cin >> p[i];
    for(int i=1 ; i<n ; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> v;
    for(int i=1 ; i<=n ; i++) v.push_back(i);
    sort(v.begin(),v.end(),[&](int a, int b){
         return p[a]<p[b];
    });
    for(int i:v){
        ans[i]=dfs(p[i],i,0,0);
        //cout << i << ' ' << ans[i] << '\n';
    }
    cout << *max_element(ans+1,ans+n+1) << '\n';

    return 0;
}

void test(){
    string ss; cin >> ss;
    int n=ss.size();
    ss='.'+ss;
    while(1){
        int t; cin >> t;
        string s=ss;
        s[t]='R';
        while(t>=1&&t<=n){
            for(int i=1 ; i<=n ; i++){
                if(i==t) cout << '(';
                cout << s[i];
                if(i==t) cout << ')';
            }
            cout << '\n';
            if(s[t]=='R') s[t]='B', t++;
            else s[t]='R', t--;
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26