제출 #1227275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227275		MarwenElarbi	Construction of Highway (JOI18_construction)	C++20	16 / 100	2095 ms	6204 KiB

construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fi first
#define se second
const int nax=2e5+7;
vector<int> adj[nax];
int colors[nax];
int parent[nax];
int main() {
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
        parent[i]=i;
        cin>>colors[i];
    }
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        //cout <<x<<" "<<y<<endl;
        int j=x;
        Tree <int> st;
        int ans=0;
        //cout << parent[j]<<" "<<j<<endl;
        while(parent[j]!=j){
            //cout<<j<<endl;
            ans+= st.order_of_key(colors[j]);
            st.insert(colors[j]);
            j=parent[j];
        }
        ans+= st.order_of_key(colors[j]);
        st.insert(colors[j]);
        /*for(auto u:st) cout <<u<<" ";
            cout <<endl;*/
        
        j=x;
        while(parent[j]!=j){
            colors[j]=colors[y];
            j=parent[j];
        }
        //cout <<parej]<<" "<<colors[y]<<endl;
        colors[j]=colors[y];
        parent[y]=x;
        /*cout <<"result:"<< ans <<endl;
        for (int j = 0; j < n; ++j) cout << colors[j]<<" ";
            cout <<endl;*/
        cout <<ans<<endl;
    }
}

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