oj.uz

Submission #44293

# Submission time Handle Problem Language Result Execution time Memory
44293 2018-03-31T09:14:16 Z Nnandi Uzastopni (COCI15_uzastopni) C++14
80 / 160
 52 ms 19052 KB 
#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)/(1<<(i+1)))*(1<<(i+1)) + (b ? 1 :0)*(1<<i) + ((prim)%(1<<(i)));
        }
        else {
            i-=bound;
            sec=((sec)/(1<<(i+1)))*(1<<(i+1)) + (b ? 1 :0)*(1<<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)) {
        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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17020 KB Output is correct
2 Correct 15 ms 17020 KB Output is correct
3 Correct 15 ms 17188 KB Output is correct
4 Correct 14 ms 17188 KB Output is correct
5 Correct 15 ms 17188 KB Output is correct
6 Incorrect 18 ms 17504 KB Output isn't correct
7 Incorrect 16 ms 17560 KB Output isn't correct
8 Incorrect 16 ms 17612 KB Output isn't correct
9 Incorrect 15 ms 17612 KB Output isn't correct
10 Incorrect 16 ms 17612 KB Output isn't correct
11 Correct 52 ms 17700 KB Output is correct
12 Correct 27 ms 17772 KB Output is correct
13 Correct 27 ms 17904 KB Output is correct
14 Incorrect 21 ms 18676 KB Output isn't correct
15 Incorrect 20 ms 19052 KB Output isn't correct
16 Incorrect 30 ms 19052 KB Output isn't correct
17 Correct 21 ms 19052 KB Output is correct
18 Correct 23 ms 19052 KB Output is correct
19 Incorrect 18 ms 19052 KB Output isn't correct
20 Incorrect 21 ms 19052 KB Output isn't correct