Submission #44285

#	Time	Username	Problem	Language	Result	Execution time	Memory
44285		Nnandi	Uzastopni (COCI15_uzastopni)	C++14	0 / 160	2 ms	464 KiB

uzastopni

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

const int maxn=10005;
const int maxv=105;
vector<int> graf[maxn];

vector<bool> dp[maxn][maxv];
int v[maxn];

void bejar(int start, int apa, set<int> volt) {
    int ez=v[start];
    if(volt.count(ez)) {
        return;
    }
    volt.insert(ez);
    dp[start][ez][ez+1]=true;
    vector<int> dag[maxv];
    dag[ez].push_back(ez+1);
    for(int s:graf[start]) {
        bejar(s,start,volt);
        for(int i=0;i<maxv;i++) {
            for(int j=i+1;j<maxv;j++) {
                if(dp[s][i][j]) {
                    dag[i].push_back(j);
                }
            }
        }
    }
    vector<int> sor;
    bool volte[maxv];
    for(int i=0;i<=ez;i++) {
        sor.resize(0);
        memset(volte,false,maxv);
        sor.push_back(i);
        int it=0;
        while(it<(int)(sor.size())) {
            int akt=sor[it]; it++;
            volte[akt]=true;
            for(int s:dag[akt]) {
                if(!volte[s]) {
                    volte[s]=true;
                    sor.push_back(s);
                }
            }
        }
        for(int d:sor) {
            if(d>ez) {
                dp[start][i][d]=true;
            }
        }
    }
    volt.erase(ez);
    return;
}

void init(int n) {
    for(int i=0;i<n;i++) {
        for(int j=0;j<maxv;j++) {
            dp[i][j].resize(maxv);
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    init(n);
    for(int i=0;i<n;i++) {
        cin>>v[i];
    }
    for(int i=0;i<n-1;i++) {
        int u, v;
        cin>>u>>v;
        u--; v--;
        graf[u].push_back(v);
    }
    set<int> s;
    bejar(0,0,s);
    int sol=0;
    for(int i=0;i<=v[0];i++) {
        for(int j=v[0]+1;j<maxv;j++) {
            if(dp[0][i][j]) {
                sol++;
            }
        }
    }
    cout<<sol<<endl;
    return 0;
}

• Subtask 1: 0 / 160