Submission #476016

#TimeUsernameProblemLanguageResultExecution timeMemory
476016innocentkittenBurza (COCI16_burza)C++14
128 / 160
412 ms452548 KiB
#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]; vector<pii> edges[21]; 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,N-1) { int a=rd(); int b=rd(); adj[a].pb(b); adj[b].pb(a); } if (K*K>=N) panic("DA"); L.pb(0); dfs(1); F0(i,H)F0(j,H6+H5)DP[i][j]=0;DP[0][0]=1; FE(v,L) F0(b,1<<K) FE(e,dual[v]) { if ((1<<e.s)&b) DP[v][b]|=DP[e.f][b^(1<<e.s)]; } cout << (DP[L.back()][(1<<K)-1]?"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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...