Submission #1185931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185931		ezzzay	Construction of Highway (JOI18_construction)	C++20	16 / 100	95 ms	840 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=4555;
int l[N];
int bit[N];
vector<int>ans;
int par[N];
vector<int>v;
int c=0;
void update(int idx, int val){
    while(idx<N){
        bit[idx]+=val;
        idx+= idx & -idx;
    }
}
int find(int idx){
    if(idx<=0)return 0;
    int s=0;
    while(idx>0){
        s+=bit[idx];
        idx -= idx & -idx;
    }
    return s;
}
void dfs(int a){
    c+= find(l[a]-1);
    update(l[a],1);
    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;
    map<int,int>tmp;
    for(int i=1;i<=n;i++){
        cin>>l[i];
        tmp[l[i]];
    }
    int id=1;
    for(auto it=tmp.begin();it!=tmp.end();it++)it->ss= id++;
    for(int i=1;i<=n;i++)l[i]=tmp[l[i]];
    par[1]=1;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        for(int j=0;j<N;j++)bit[j]=0;
        c=0;
        par[b]=a;
        dfs(a);
        fun(a,b);
        ans.pb(c);
    }
    for(auto a:ans)cout<<a<<endl;
}

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