Submission #486429

#	Time	Username	Problem	Language	Result	Execution time	Memory
486429		blue	Construction of Highway (JOI18_construction)	C++17	7 / 100	2081 ms	408 KiB

construction

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    cin >> N;

    int C[1+N];
    for(int i = 1; i <= N; i++) cin >> C[i];

    int P[1+N];
    P[0] = P[1] = 0;

    for(int j = 1; j <= N-1; j++)
    {
        vector<int> lst;

        int A, B;
        cin >> A >> B;

        for(int q = A; q != 0; q = P[q])
            lst.push_back(C[q]);

        reverse(lst.begin(), lst.end());

        int ans = 0;

        for(int i = 0; i < int(lst.size()); i++)
            for(int j = i+1; j < int(lst.size()); j++)
                ans += lst[i] > lst[j];

        cout << ans << '\n';

        for(int k = A; k != 0; k = P[k])
            C[k] = C[B];

        P[B] = A;
    }
}

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