Submission #44294

#	Time	Username	Problem	Language	Result	Execution time	Memory
44294		Nnandi	Uzastopni (COCI15_uzastopni)	C++14	80 / 160	51 ms	18176 KiB

uzastopni

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

struct Mydata {
    long long prim, sec;
    Mydata() {
        prim=0LL;
        sec=0LL;
    }
    bool get_elem(int i) {
        if(i<bound) {
            return ((prim>>i)%2==1);
        }
        else {
            i-=bound;
            return ((sec>>i)%2==1);
        }
    }
    void set_elem(int i, bool b) {
        if(i<bound) {
            prim=((prim>>(i+1))<<(i+1)) + ((b ? 1LL :0LL)<<i) + ((prim)%(1<<i));
        }
        else {
            i-=bound;
            sec=((sec>>(i+1))<<(i+1)) + ((b ? 1LL :0LL)<<i) + ((sec)%(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);
    dp[start][ez].set_elem(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].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];
    }
    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].get_elem(j)) {
                sol++;
            }
        }
    }
    cout<<sol<<endl;
    return 0;
}

• Subtask 1: 80 / 160