제출 #1284184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284184		Trn115	Construction of Highway (JOI18_construction)	C++17	7 / 100	2095 ms	580 KiB

construction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int N = 1e5+5;

int n;
int c[N];
int par[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];

    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        par[b] = a;
        vector<int> seq;
        int v = a;
        ll res = 0;
        while (v != 0) {
            for (int x : seq) res += c[v] > x;
            seq.push_back(c[v]);
            c[v] = c[b];
            v = par[v];
        }
        cout << res << "\n";
    }
}

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