Submission #797923

#	Time	Username	Problem	Language	Result	Execution time	Memory
797923		vjudge1	Construction of Highway (JOI18_construction)	C++17	0 / 100	0 ms	212 KiB

construction

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5000;

int n;
int p[N];
int C[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> C[i];
    for(int i = 1; i <= n - 1; i++) {
        int A, B;
        cin >> A >> B;
        vector<int> vals;
        int cur = A;
        while(cur) {
            vals.push_back(cur);
            cur = p[cur];
        }
        reverse(vals.begin(), vals.end());
        ll res = 0;
        int bound = 0;
        for(int j : vals) {
            while(C[vals[bound]] > C[j]) {
                bound++;
            }
            res += bound;
        }

        p[B] = A;
        cur = A;
        while(cur) {
            C[cur] = C[B];
            cur = p[cur];
        }
        cout << res << '\n';
    }
}

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