oj.uz

Submission #476023

# Submission time Handle Problem Language Result Execution time Memory
476023 2021-09-24T15:35:04 Z innocentkitten Burza (COCI16_burza) C++14
160 / 160
 383 ms 452504 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define p push
#define ins insert
#define t top
#define fr front

#define T1 10
#define T2 100
#define T3 1000
#define T4 10000
#define T5 100000
#define T6 1000000

#define H1 11
#define H2 105
#define H3 1010
#define H4 10010
#define H5 100010
#define H6 1000010

#define H 4*H2
#define HH 43

#define woof 31051
#define mod 998244353
#define MOD 1000000007
#define lnf 0
#define inf 1069999999
#define INF 2099999999
#define LNF 1e18

// sacrilege
#define F0(x,n) for(int x = 0; x < n; ++x)
#define FR0(x,L,R) for(int x = L; x < R; ++x)
#define R0(x,n) for(int x = n-1; x >= 0; --x)
#define F1(x,n) for(int x = 1; x <= n; ++x)
#define FR1(x,L,R) for(int x = L; x <= R; ++x)
#define R1(x,n) for(int x = n; x >= 1; --x)
#define RR(x,L,R) for(int x = R; x >= L; --x)
#define FE(x,ls) for(auto x : ls)
#define ub(x,v) upper_bound(x.begin(),x.end(),v)
#define lb(x,v) lower_bound(x.begin(),x.end(),v)


using namespace std;
mt19937 mr(time(0));
typedef long long int ll;
typedef string str;
typedef double dbl;
struct LL {

    static const ll m = mod; // set to LNF for nomod
    long long int val;

    LL(ll v) {val=reduce(v);};
    LL(int v) {val=reduce((ll)v);};
    LL() {val=0;};
    ~LL(){};
    LL(const LL& l) {val=l.val;};
    LL& operator=(int l) {val=l; return *this;}
    LL& operator=(ll l) {val=l; return *this;}
    LL& operator=(LL l) {val=l.val; return *this;}

    static long long int reduce(ll x, ll md = m) {
        x %= md;
        while (x >= md) x-=md;
        while (x < 0) x+=md;
        return x;
    }

    bool operator<(const LL& b) { return val<b.val; }
    bool operator<=(const LL& b) { return val<=b.val; }
    bool operator!=(const LL& b) { return val!=b.val; }
    bool operator==(const LL& b) { return val==b.val; }
    bool operator>=(const LL& b) { return val>=b.val; }
    bool operator>(const LL& b) { return val>b.val; }

    LL operator+(const LL& b) { return LL(val+b.val); }
    LL operator+(const ll& b) { return (*this+LL(b)); }
    LL& operator+=(const LL& b) { return (*this=*this+b); }
    LL& operator+=(const ll& b) { return (*this=*this+b); }

    LL operator-(const LL& b) { return LL(val-b.val); }
    LL operator-(const ll& b) { return (*this-LL(b)); }
    LL& operator-=(const LL& b) { return (*this=*this-b); }
    LL& operator-=(const ll& b) { return (*this=*this-b); }

    LL operator*(const LL& b) { return LL(val*b.val); }
    LL operator*(const ll& b) { return (*this*LL(b)); }
    LL& operator*=(const LL& b) { return (*this=*this*b); }
    LL& operator*=(const ll& b) { return (*this=*this*b); }

    static LL exp(const LL& x, const ll& y){
        ll z = y;
        z = reduce(z,m-1);
        LL ret = 1;
        LL w = x;
        while (z) {
            if (z&1) ret *= w;
            z >>= 1; w *= w;
        }
        return ret;
    }
    LL& operator^=(ll y) { return (*this=LL(val^y)); }

    LL operator/(const LL& b) { return ((*this)*exp(b,-1)); }
    LL operator/(const ll& b) { return (*this/LL(b)); }
    LL operator/=(const LL& b) { return ((*this)*=exp(b,-1)); }
    LL& operator/=(const ll& b) { return (*this=*this/LL(b)); }

}; ostream& operator<<(ostream& os, const LL& obj) { return os << obj.val; }
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<int,LL> piL;
typedef pair<ll,ll> pll;
typedef pair<LL,LL> pLL;
typedef pair<dbl,dbl> pdd;
using namespace std;

ll cases,N,M,Q,K,X,Y;

ll rd() {ll x;cin>>x; return x;}
dbl rdd() {dbl x;cin>>x; return x;}
void fl() {cout.flush();}

void panic(ll out) {
    cout << out << endl;
    exit(0);
}

void panic(str out) {
    cout << out << endl;
    exit(0);
}


vector<int> adj[H];
int T[H]; int D[H]; int t = 0;
vector<int> L;
vector<pii> dual[H];

void dfs(int v, int d=-1) {
    D[v] = ++d; T[v]=++t;
    if (d==K) L.pb(T[v]);
    else FE(u,adj[v]) if (T[u]==0) dfs(u,d);
    if (d) dual[L.back()].pb(mp(*--lb(L,T[v]),d-1));
}

bool DP[H][H6+H5];

void read() {
    N=rd();K=rd();
    F0(i,H) {adj[i].clear();dual[i].clear();T[i]=0;D[i]=0;} L.clear();
    F0(i,N-1) {
        int a=rd(); int b=rd();
        adj[a].pb(b);
        adj[b].pb(a);
    }
    if (K*K>=N) panic("DA");
    F0(i,H)F0(j,H6+H5)DP[i][j]=0;DP[0][0]=1;
    L.pb(0);
    dfs(1);
    FE(v,L) if(v) F0(b,1<<K) FE(e,dual[v]) {
        if ((1<<e.s)&b) DP[v][b]|=DP[e.f][b^(1<<e.s)];
    }
    bool ret = 0; F0(b,1<<K) ret|=DP[L.back()][b];
    cout << (ret?"DA":"NE") << endl;
}

int main() {

    bool trials = 0;
    bool interactive = 0;

    if (!interactive) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    }

    if (trials) cases=rd();
    else cases=1;
    while (cases--) {
        read();
    }

}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 452320 KB Output is correct
2 Correct 299 ms 452284 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 173 ms 452396 KB Output is correct
6 Correct 184 ms 452276 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 452292 KB Output is correct
2 Correct 299 ms 452400 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 299 ms 452364 KB Output is correct
6 Correct 167 ms 452344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 452504 KB Output is correct
2 Correct 305 ms 452468 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 169 ms 452396 KB Output is correct
6 Correct 166 ms 452292 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 452336 KB Output is correct
2 Correct 308 ms 452404 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 178 ms 452364 KB Output is correct
6 Correct 171 ms 452420 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 452292 KB Output is correct
2 Correct 306 ms 452292 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 178 ms 452312 KB Output is correct
6 Correct 178 ms 452308 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 452420 KB Output is correct
2 Correct 301 ms 452420 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 168 ms 452300 KB Output is correct
6 Correct 163 ms 452312 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 452292 KB Output is correct
2 Correct 314 ms 452336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 319 ms 452380 KB Output is correct
6 Correct 171 ms 452404 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 452376 KB Output is correct
2 Correct 311 ms 452404 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 168 ms 452356 KB Output is correct
6 Correct 175 ms 452360 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 452352 KB Output is correct
2 Correct 319 ms 452404 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 165 ms 452300 KB Output is correct
6 Correct 169 ms 452400 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 452376 KB Output is correct
2 Correct 383 ms 452384 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 244 ms 452364 KB Output is correct
6 Correct 179 ms 452356 KB Output is correct