oj.uz

Submission #44304

# Submission time Handle Problem Language Result Execution time Memory
44304 2018-03-31T11:02:22 Z Nnandi Uzastopni (COCI15_uzastopni) C++14
160 / 160
 58 ms 17916 KB 
#include <bits/stdc++.h>
#define bound 28
using namespace std;

struct Mydata {
    int tab[4];
    Mydata() {
        for(int i=0;i<4;i++) tab[i]=0;
    }
    bool get_elem(int i) {
        int z=i/bound;
        i=i%bound;
        return ((tab[z]>>i)%2==1);
    }
    void set_elem(int i, bool b) {
        int z=i/bound;
        i=i%bound;
        int akt=tab[z];
        tab[z]=((akt>>(i+1))<<(i+1)) + ((b ? 1 :0)<<i) + ((akt)%(1<<i));
        return;
    }
};

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

Mydata dp[maxn][maxv];
int v[maxn];

void bejar(int start, int apa, set<int> &volt) {
    int ez=v[start];
    if(volt.count(ez)>0) {
        return;
    }
    volt.insert(ez);
    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].get_elem(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].set_elem(d,true);
            }
        }
    }
    volt.erase(ez);
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>v[i];
        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;
    s.clear();
    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].get_elem(j)) {
                sol++;
            }
        }
    }
    cout<<sol<<endl;
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17016 KB Output is correct
2 Correct 16 ms 17016 KB Output is correct
3 Correct 16 ms 17048 KB Output is correct
4 Correct 15 ms 17048 KB Output is correct
5 Correct 16 ms 17168 KB Output is correct
6 Correct 17 ms 17236 KB Output is correct
7 Correct 17 ms 17364 KB Output is correct
8 Correct 22 ms 17380 KB Output is correct
9 Correct 19 ms 17380 KB Output is correct
10 Correct 16 ms 17380 KB Output is correct
11 Correct 58 ms 17472 KB Output is correct
12 Correct 29 ms 17488 KB Output is correct
13 Correct 27 ms 17492 KB Output is correct
14 Correct 20 ms 17872 KB Output is correct
15 Correct 20 ms 17916 KB Output is correct
16 Correct 20 ms 17916 KB Output is correct
17 Correct 34 ms 17916 KB Output is correct
18 Correct 26 ms 17916 KB Output is correct
19 Correct 28 ms 17916 KB Output is correct
20 Correct 19 ms 17916 KB Output is correct