Submission #1185929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185929		ezzzay	Construction of Highway (JOI18_construction)	C++20	7 / 100	2095 ms	568 KiB

construction

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int l[N];
vector<int>ans;
int par[N];
vector<int>v;
void dfs(int a){
    v.pb(l[a]);
    if(a==1)return;
    dfs(par[a]);
}
void fun(int a, int b){
    l[a]=l[b];
    if(b==1)return;
    fun(par[a],a);
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>l[i];
    par[1]=1;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        v.clear();
        int c=0;
        par[b]=a;
        dfs(a);
        
        for(int j=0;j<v.size();j++){
            for(int k=j+1;k<v.size();k++){
                if(v[j]<v[k])c++;
            }
        }
        fun(a,b);
        ans.pb(c);
    }
    for(auto a:ans)cout<<a<<endl;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84