Submission #882548

#	Time	Username	Problem	Language	Result	Execution time	Memory
882548		iskhakkutbilim	Construction of Highway (JOI18_construction)	C++17	16 / 100	2104 ms	73172 KiB

construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ff first
#define ss second
#define all(a) (a.begin(), a.end())


const int mod = 1e9 + 7;
const int N = 1e5;
int n, c[N+10];
vector<int> g[N+10], group[N+10];
int shortest[N+10];
int par[N+10];


typedef tree<int, null_type, less_equal<int> ,rb_tree_tag, tree_order_statistics_node_update> ordered_set; 

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n; i++){
		cin >> c[i];
		shortest[i] = -1;
	}
	int q = n-1;
	shortest[1] = 0;
	par[1] = -1; 
	group[1].push_back(1);
	while(q--){
		int a, b; cin >> a >> b;
		int cost = 0;
		ordered_set st;
		for(int s : group[a]){
			int it = st.order_of_key(c[s] + 1);
			cost+= (st.size() - it);
			st.insert(c[s]);
		}
		
		g[a].push_back(b);
		for(int x : group[a]){
			group[b].push_back(x);
		}
		group[b].push_back(b);
		if(shortest[b] == -1 or shortest[b] > shortest[a]+1){
			shortest[b] = shortest[a] + 1;
			par[b] = a;
		}
		int parent = a;
		while(parent != -1){
			c[parent] = c[b];
			parent = par[parent];
		}
		cout << cost << '\n';
	}
	return 0;
}

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