oj.uz

Submission #166854

# Submission time Handle Problem Language Result Execution time Memory
166854 2019-12-04T11:23:52 Z Atill83 Burza (COCI16_burza) C++14
160 / 160
 398 ms 37356 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3000;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, k;
vector<int> adj[MAXN];
int dep[MAXN];
int gir[MAXN];
int cik[MAXN];
int yapraksayi = 0;
bool dp[405][(1<<20)];
vector<int> q[MAXN];
void dfs(int a, int par){
    if(par != -1) dep[a] = dep[par] + 1;
    if(dep[a] == k){
        gir[a] = yapraksayi;
        cik[a] = yapraksayi;
        yapraksayi++;
        return;
    }
    gir[a] = yapraksayi;
    for(int i: adj[a]){
        if(i != par) dfs(i, a);
    }
    cik[a] = yapraksayi - 1;
}

bool do_it(){
    for(int i = 2; i <= n; i++){
        if(!dep[i]) continue;
        dep[i]--;
        q[gir[i]].push_back(i);
        //cout<<gir[i]<<endl;
        //cout<<dep[i]<<endl;
    }
    //return 0;
    dp[0][0] = 1;

    for(int i = 0; i < yapraksayi; i++){
        for(int j = 0; j < (1<<20); j++){
            if(!dp[i][j]) continue;
            for(int k: q[i]){
                if(((j>>dep[k]) & 1) == 0){
                    dp[cik[k] + 1][j | (1<<dep[k])] = 1;
                    //cout<<cik[k] + 1<<endl;
                }
            }
        }
    }
    for(int i = 0; i < (1<<20); i++){
        if(dp[yapraksayi][i]) return 1;
    }
    return 0;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n>>k;

    if(k*(k + 1) >= 2*n){
        cout<<"DA"<<endl;
        return 0;
    }
    
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dep[1] = 0;
    dfs(1, -1);
    
    cout<<(do_it() ? "DA" : "NE")<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1120 KB Output is correct
2 Correct 151 ms 2812 KB Output is correct
3 Correct 354 ms 32864 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 307 ms 1244 KB Output is correct
6 Correct 44 ms 636 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 2936 KB Output is correct
2 Correct 133 ms 2812 KB Output is correct
3 Correct 315 ms 10548 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 157 ms 3176 KB Output is correct
6 Correct 338 ms 1292 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3132 KB Output is correct
2 Correct 141 ms 2680 KB Output is correct
3 Correct 398 ms 35324 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 215 ms 1048 KB Output is correct
6 Correct 59 ms 632 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 1512 KB Output is correct
2 Correct 187 ms 3448 KB Output is correct
3 Correct 320 ms 20168 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 183 ms 1016 KB Output is correct
6 Correct 34 ms 632 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 2424 KB Output is correct
2 Correct 140 ms 3064 KB Output is correct
3 Correct 344 ms 34256 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 289 ms 1244 KB Output is correct
6 Correct 212 ms 1148 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 2880 KB Output is correct
2 Correct 138 ms 2928 KB Output is correct
3 Correct 364 ms 37356 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 311 ms 1272 KB Output is correct
6 Correct 193 ms 908 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 3212 KB Output is correct
2 Correct 146 ms 3064 KB Output is correct
3 Correct 318 ms 14108 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 150 ms 3448 KB Output is correct
6 Correct 220 ms 1144 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 1576 KB Output is correct
2 Correct 155 ms 2936 KB Output is correct
3 Correct 322 ms 8696 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 167 ms 888 KB Output is correct
6 Correct 313 ms 1164 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 888 KB Output is correct
2 Correct 170 ms 3196 KB Output is correct
3 Correct 340 ms 16796 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 183 ms 888 KB Output is correct
6 Correct 260 ms 1144 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 1864 KB Output is correct
2 Correct 168 ms 3192 KB Output is correct
3 Correct 316 ms 22184 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 103 ms 1784 KB Output is correct
6 Correct 131 ms 760 KB Output is correct