oj.uz

답안 #915651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915651 2024-01-24T13:04:13 Z 0xZero Burza (COCI16_burza) C++17
0 / 160
 1000 ms 3856 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
#define str string
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<db,db>
#define f first
#define s second
#define vi vector<int>
#define vl vector<ll>
#define vd vector<db>
#define vpi vector<pi>
#define vpl vector<pl>
#define vpd vector<pd>
#define vvi vector<vi>
#define vvl vector<vl>
#define pqu priority_queue
#define gtr greater
#define V vector
#define bg begin
#define rbg rbegin
#define ub upper_bound
#define lb lower_bound
#define elif else if
#define spc <<' '<<
#define nl <<'\n'
#define parity __builtin_parity
#define parityll __builtin_parityll
#define IOS cin.tie(0)->sync_with_stdio(0)
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define clz __builtin_clz
#define clzll __builtin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define gcd __gcd
#define lcm(a,b) (a)/gcd((a),(b))*(b)
#define all(x) (x).bg(),(x).end()
#define rall(x) (x).rbg(),(x).rend()
#define sz(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define R0F(i,a) ROF(i,a,0)
#define rep(a) F0R(_,a)
#define each(a,x) for(auto &a:x)
#define sor(x) sort(all(x))
#define rsor(x) sort(rall(x))
#define uniq(x) sor(x); (x).erase(unique(all(x)),(x).end())
#define rev(x) reverse(all(x))
#define sum(x) accumulate(all(x),0LL)
#define maxi(x) max_element(all(x))-(x).bg()
#define mini(x) min_element(all(x))-(x).bg()
#define fi(x,a) fill(all(x),a)
#define coutprec(x) cout<<fixed<<setprecision(x)
#define debug(x) cerr<<#x<<':'<<x<<'\n'

template<class T> using pqg=pqu<T,V<T>,gtr<T>>;
template<typename... Args> void re(Args&... args) { ((cin >> args), ...); }
template<typename T> void reV(T& a) {each(b,a)cin>>b;}
template<typename... Args> void pr(Args... args) { ((cout << args << " "), ...); cout<<'\n'; }
template<typename T> void prV(T& a) {each(b,a)cout<<b<<' ';cout nl;}
#define bs bitset<mx>
const int mx=400;
int n, k;
vi adj[mx];
int dep[mx], mxd[mx]={0};

bool cmp (const bs & a, const bs & b){
    F0R(i, 400)if(a[i]!=b[i])return a[i]<b[i];
    return 0;
}
map<bs, bool, bool (*)(const bs &, const bs &)> dp(cmp);

void dfs(int u, int e){
    mxd[u]=dep[u];
    each(i, adj[u])if(i!=e){
        dep[i]=dep[u]+1;
        dfs(i, u);
        mxd[u]=max(mxd[u], mxd[i]);
    }
}

bool f(int x, int y, const bs &b){
    if(x==y)return 0;
    if(dp.count(b))return dp[b];
    bs c(0);
    bool ans=0;
    F0R(i, n)if(b[i])each(j, adj[i])if(dep[j]>dep[i] && mxd[j]>=y)c[j]=1;
    if(c.count()<=1)return 1;
    F0R(i, n)if(c[i]){
        c[i]=0;
        ans|=f(x+1, y, c);
        c[i]=1;
    }
    dp[b]=ans;
    return ans;
}

int main(){
    IOS;
    re(n, k);
    rep(n-1){
        int a, b;
        re(a, b);
        a--;b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dep[0]=0;
    dfs(0, -1);
    bs b(1);
    if(f(0, k, b))pr("DA");
    else pr("NE");
    return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 2160 KB Output is correct
2 Execution timed out 1020 ms 3244 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1066 ms 3408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1062 ms 3552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1025 ms 3272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1062 ms 3016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 3856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1046 ms 3092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1055 ms 3336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 2512 KB Output is correct
2 Execution timed out 1070 ms 3556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1029 ms 3456 KB Time limit exceeded
2 Halted 0 ms 0 KB -