제출 #783211

#제출 시각아이디문제언어결과실행 시간메모리
783211KahouConstruction of Highway (JOI18_construction)C++14
16 / 100
99 ms724 KiB
/* In the name of God, aka Allah */ #include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 5050; int n, a[N], par[N], fen[N]; pii P[N]; pii E[N]; ll get(int i) { ll out = 0; for (; i > 0; i -= i&-i) out += fen[i]; return out; } void upd(int i, int x) { for (; i <= n; i += i&-i) fen[i] += x; } void solve() { cin >> n; for (int u = 1; u <= n; u++) { cin >> a[u]; P[u] = {a[u], u}; } sort(P+1, P+n+1); int t = 0; for (int i = 1; i <= n; i++) { if (P[i].F != P[i-1].F) t++; a[P[i].S] = t; } for (int i = 1; i <= n-1; i++) { int u, v; cin >> u >> v; E[i] = {u, v}; par[v] = u; } for (int i = 1; i <= n-1; i++) { int u = E[i].F; for (int x = 1; x <= n; x++) fen[x] = 0; ll out = 0; while (u) { out += get(a[u]-1); upd(a[u], 1); u = par[u]; } u = E[i].F; while (u) { a[u] = a[E[i].S]; u = par[u]; } cout << out << endl; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...