oj.uz

Submission #797923

# Submission time Handle Problem Language Result Execution time Memory
797923 2023-07-30T07:09:36 Z vjudge1 Construction of Highway (JOI18_construction) C++17
0 / 100
 0 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -