oj.uz

Submission #44294

# Submission time Handle Problem Language Result Execution time Memory
44294 2018-03-31T09:32:55 Z Nnandi Uzastopni (COCI15_uzastopni) C++14
80 / 160
 51 ms 18176 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>>(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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17016 KB Output is correct
2 Correct 14 ms 17128 KB Output is correct
3 Correct 14 ms 17128 KB Output is correct
4 Correct 14 ms 17128 KB Output is correct
5 Correct 15 ms 17128 KB Output is correct
6 Incorrect 16 ms 17672 KB Output isn't correct
7 Incorrect 16 ms 17672 KB Output isn't correct
8 Incorrect 16 ms 17672 KB Output isn't correct
9 Incorrect 15 ms 17672 KB Output isn't correct
10 Incorrect 15 ms 17672 KB Output isn't correct
11 Correct 51 ms 17672 KB Output is correct
12 Correct 27 ms 17672 KB Output is correct
13 Correct 23 ms 17672 KB Output is correct
14 Incorrect 22 ms 18172 KB Output isn't correct
15 Incorrect 20 ms 18176 KB Output isn't correct
16 Incorrect 24 ms 18176 KB Output isn't correct
17 Correct 23 ms 18176 KB Output is correct
18 Correct 33 ms 18176 KB Output is correct
19 Incorrect 26 ms 18176 KB Output isn't correct
20 Incorrect 19 ms 18176 KB Output isn't correct