제출 #1310242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310242		mat_jur	Construction of Highway (JOI18_construction)	C++20	7 / 100	2096 ms	676 KiB

construction

#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> c(n);
	map<int, int> remap;
	for (int &x : c) {
		cin >> x;
		remap[x];
	}

	int cnt = 0;
	for (auto &e : remap)
		e.se = cnt++;

	for (int &x : c) x = remap[x];

	vector<int> parent(n, -1);
	for (int i = 0; i < n-1; ++i) {
		int a, b;
		 cin >> a >> b;
		 --a; --b;
		parent[b] = a;

		vector<int> cnt(n);
		
		ll res = 0;

		debug(parent);
		debug(c);
		while (a != -1) {
			int x = c[a];
			for (int y = 0; y < x; ++y) res += cnt[y];
			cnt[x]++;
			c[a] = c[b];
			a = parent[a];
		}

		cout << res << '\n';
	}
	
	return 0;
}

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