Submission #465377

#	Time	Username	Problem	Language	Result	Execution time	Memory
465377		JovanB	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	9 ms	4812 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 10000;

bool L[N+5][105], R[N+5][105];
int val[N+5];
vector <int> graf[N+5];

void dfs(int v){
    vector <int> vl, vr;
    L[v][val[v]] = R[v][val[v]] = 1;
    for(auto c : graf[v]){
        dfs(c);
        if(val[c] < val[v]) vl.push_back(c);
        else if(val[c] > val[v]) vr.push_back(c);
    }
    sort(vl.begin(), vl.end(), [](int a, int b){ return val[a] > val[b]; });
    sort(vr.begin(), vr.end(), [](int a, int b){ return val[a] < val[b]; });
    for(auto c : vl) for(int l=val[c]; l>=1; l--) for(int r=val[c]; r<val[v]; r++) L[v][l] |= L[v][r+1] & L[c][l] & R[c][r];
    for(auto c : vr) for(int l=val[v]+1; l<=val[c]; l++) for(int r=val[c]; r<=100; r++) R[v][r] |= R[v][l-1] & L[c][l] & R[c][r];
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
    }
    dfs(1);
    int res = 0;
    for(int i=1; i<=val[1]; i++) for(int j=val[1]; j<=100; j++) res += (L[1][i] & R[1][j]);
    cout << res << "\n";
    return 0;
}

• Subtask 1: 160 / 160