oj.uz

Submission #483618

# Submission time Handle Problem Language Result Execution time Memory
483618 2021-10-31T07:42:02 Z EntropyX Burza (COCI16_burza) C++17
160 / 160
 137 ms 12800 KB 
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define iiordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;

//Bit Functions
#define gcd __gcd
#define lsb __builtin_ffs
#define ldz __builtin_clz
#define tlz __builtin_ctz
#define stc __builtin_popcount
#define prtb(n) cout << bitset<20>(n) << "\n";

//Debugging
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define what_is(x) cerr << #x << " is " << x << endl;
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

//STL Declarations
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<long long int>
#define vvl vector<vl>
#define vb vector<bool>
#define pii pair<int,int>
#define fr first
#define sc second
#define u_s unordered_set
#define ump unordered_map
#define ins insert
#define p_q(x) priority_queue<x>

//STL Functions
#define mt make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define muq make_unique
#define all(x) x.begin(),x.end()
#define rot(vec,k) rotate(vec.begin(), vec.begin() + k, vec.end());
#define bs(vec,key) binary_search(all(vec), key)
#define parti(vec,p) partition_point(all(vec), p) - vec.begin()
#define srt(cnt) sort(all(cnt))
#define lb(cnt,x) lower_bound(all(cnt),x)
#define ub(cnt,x) upper_bound(all(cnt),x)
#define mxm(cnt) *max_element(all(cnt))
#define mnm(cnt) *min_element(all(cnt))
#define mxmptr(cnt) max_element(all(cnt))
#define mnmptr(cnt) min_element(all(cnt))
#define rev(cnt) reverse(all(cnt))
#define accum(cnt) accumulate(all(cnt),0)
#define look(cnt) for(auto c:cnt) cout<<c<<" "; cout<<"\n";
#define pre(x,cont) find(all(cont),x)!=cont.end()
#define pb push_back

//Input Functions
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << t<<" "; return os << endl; }
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << v.first << " " << v.second ; }

typedef long long int ll;
ll mod = 10000000007;

//Generalised Sum Function
int sum() { return 0; }
template<typename T, typename... Args>
T sum(T a, Args... args) { return a + sum(args...); }

vector<int> seive(int N){
    vector<bool> visited(N+1,false);
    vi pr;
    for(int i=2;i<=N;i++){
        if(!visited[i]){
            int j = i;
            pr.pb(j);
            while(j<=N){visited[j] = true;j+=i;}}}
    return pr;
}
ll ceil(ll a,ll b){
    if(b<0)a=-a,b=-b;
    if(a>=0)return (a+b-1)/b;
    return a/b;
}
long long bpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll inverse(ll a,ll m=mod)
{
    return bpow(a,m-2,m);
}
vvl matmul(const vvl &a,const vvl &b,ll M=mod)
{
    int n=a.size(),m=a[0].size(),l=b[0].size();
    assert(m==b.size());
    vvl c(n,vl(l,0));
    rep(i,0,n)
        rep(j,0,l)
            rep(k,0,m)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%M;
            }
    return c;
}
vvl matpow(vvl a,ll p,ll M=mod)
{
    assert(a.size()==a[0].size());
    int n=a.size();
    vvl res(n,vl(n,0));
    rep(i,0,n)   res[i][i]=1;
    while(p>0)
    {
        if(p&1) res=matmul(res,a,M);
        a=matmul(a,a,M);
        p>>=1;
    }
    return res;
}

const ll COMBINATION_SIZE = 300005;
const ll MOD = 1e9+7;

struct Combination {
    long long fac[COMBINATION_SIZE], inv[COMBINATION_SIZE];
    bool built = 0;
    void build(){
        assert(MOD >= COMBINATION_SIZE);
        fac[0] = 1;
        for(int i = 1; i < COMBINATION_SIZE; i++) {
            fac[i] = fac[i - 1] * i % MOD;
        }
        inv[COMBINATION_SIZE - 1] = inverse(fac[COMBINATION_SIZE - 1], MOD);
        for(int i = COMBINATION_SIZE - 2; i >= 0; i--) {
            inv[i] = inv[i + 1] * (i + 1) % MOD;
        }
    }
    long long C(int x, int y){
        if(y < 0 || y > x) {
            return 0;
        }
        if(!built) {
            built = 1;
            build();
        }
        return fac[x] * inv[y] % MOD * inv[x-y] % MOD;
    }
} comb;

void setIO(string s) { // the argument is the filename without the extension
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

int main(){ _
    int n,k;cin >> n >> k;
    vvi adj(n+1);
    rep(i,1,n){
        int a,b;cin >> a >> b;
        adj[a].pb(b);adj[b].pb(a);
    }
    if(k*k>=n){
        cout << "DA\n";
    }
    else{
        vvi adj2(n+1);
        vi depth(n+1,0);
        vi visited(n+1,false);
        function<bool(int)> dfs = [&](int node){
            visited[node] = true;
            if(depth[node] == k){
                return true;
            }
            bool ret = false;
            for(auto c:adj[node]){
                if(!visited[c]){
                    depth[c] = depth[node] + 1;
                    if(dfs(c)) {
                        adj2[node].pb(c);
                        ret = true;
                    }
                }
            }
            return ret;
        };
        depth[1] = 0;
        dfs(1);
        fill(all(visited),false);
        // adj2 has been calculated!
        vi L(n+1,INT_MAX);
        vi R(n+1,-1);
        int leaves = 0;
        vvi ancestors(n+1);
        function<void(int)> dfs2 = [&](int node){
            visited[node] = true;
            bool leaf = true;
            for(auto c:adj2[node]){
                if(!visited[c]){
                    leaf = false;
                    dfs2(c);
                    L[node] = min(L[node],L[c]);
                    R[node] = max(R[node],R[c]);
                }
            }
            if(leaf){
                L[node] = leaves;
                R[node] = leaves;
                leaves++;
            }
//            cout << node << " " << L[node] << " " << R[node] << "\n";
            if(node!=1)
                ancestors[R[node]].pb(node);
        };
        dfs2(1);
        bool dp[(1<<k)][leaves+1];
        memset(dp,0,sizeof dp);
        dp[0][0] = true;
        bool ok = false;
        for(int i=1;i<(1<<k);i++){
            for(int j=1;j<=leaves;j++){
                for(auto anc:ancestors[j-1]){
                    if(i&(1<<(depth[anc]-1))){
                        dp[i][j] = dp[i][j] or (dp[i^(1<<(depth[anc]-1))][L[anc]]);
                    }
                }
            }
            if(dp[i][leaves])
                ok = true;
        }
        if(ok){
            cout << "DA\n";
        }
        else{
            cout << "NE\n";
        }
    }
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from burza.cpp:4:
burza.cpp: In function 'std::vector<std::vector<long long int> > matmul(const std::vector<std::vector<long long int> >&, const std::vector<std::vector<long long int> >&, ll)':
burza.cpp:111:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     assert(m==b.size());
      |            ~^~~~~~~~~~
burza.cpp: In function 'void setIO(std::string)':
burza.cpp:166:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:167:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1868 KB Output is correct
2 Correct 119 ms 12428 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 10876 KB Output is correct
2 Correct 137 ms 10444 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 114 ms 10572 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 10748 KB Output is correct
2 Correct 118 ms 10700 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4364 KB Output is correct
2 Correct 116 ms 12800 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9164 KB Output is correct
2 Correct 115 ms 10188 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 11388 KB Output is correct
2 Correct 119 ms 9972 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 11004 KB Output is correct
2 Correct 110 ms 10360 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 121 ms 9664 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3276 KB Output is correct
2 Correct 128 ms 11776 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1504 KB Output is correct
2 Correct 117 ms 11904 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 232 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4324 KB Output is correct
2 Correct 124 ms 12100 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 54 ms 4484 KB Output is correct
6 Correct 0 ms 332 KB Output is correct