oj.uz

Submission #918395

# Submission time Handle Problem Language Result Execution time Memory
918395 2024-01-29T19:06:47 Z Ludissey Burza (COCI16_burza) C++14
0 / 160
 2 ms 600 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int LOG=10;
vector<vector<int>> adj;
vector<int> depth;
vector<int> kthDepth;
vector<vector<int>> parent;
int k;

int comf(int a){
    return (((a+49)/50)-1);
}

vector<int> addNumb(int a, vector<int> mask){
    int i=comf(a);
    mask[i]+=(1<<(a-(i*50)));
    return mask;
}

vector<int> optimal;
bool compMask(vector<int> a, vector<int> b){
    for (int i = 1; i <= 8; i++) { if(a[i]!=b[i]) return 0; }
    return 1;
}
map<int,map<vector<int>, int>> memo;
bool dp(int d, vector<int> mask){
    if(memo[d].find(mask)!=memo[d].end()) return memo[d][mask];
    if(d==k) return compMask(mask, optimal);
    map<int,vector<int>> mp;
    int depthDf=k-d;
    for (int i = 0; i < kthDepth.size(); i++)
    {
        int u=kthDepth[i];
        for (int j = LOG-1; j >= 0; j--) if(depthDf&(1<<j)) u=parent[u][j];
        vector<int> empty(8,0);
        if(mp.find(u)==mp.end()){
            mp[u]=empty;
        }
        empty=mp[u];
        empty[comf(kthDepth[i])]=empty[comf(kthDepth[i])]+(1<<(kthDepth[i]-(comf(kthDepth[i])*50)));
        mp[u]=empty;
    }
    for (auto u : mp)
    {
        if(dp(d+1, u.second)) return memo[d][mask]=true;
    }
    if(mp.size()==0) return memo[d][mask]=true;
    return memo[d][mask]=false;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,K; cin >> n >> K;
    k=K;
    parent.resize(n+1, vector<int>(LOG));
    parent[1][0]=1;
    adj.resize(n+1);
    depth.resize(n+1);
	for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    optimal.resize(8,0);
    queue<pair<int,int>> queue;
    vector<bool> visited(n+1); 
    queue.push({1,0});
    while(!queue.empty()){
        int x=queue.front().first,d=queue.front().second; queue.pop();
        depth[x]=d;
        if(d==K) {
            optimal=addNumb(x,optimal);
            kthDepth.push_back(x);
        }
        visited[x]=true;
        for (auto u : adj[x]) {
            if(visited[u]) continue;
            queue.push({u,d+1});
            parent[u][0]=x;
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j < LOG; j++) parent[i][j]=parent[parent[i][j-1]][j-1];
    vector<int> empty(8,0);
    bool DA=dp(0, empty);
    if(DA) cout << "DA\n";
    else cout << "NE\n";
    return 0;
}

Compilation message

burza.cpp: In function 'bool dp(long long int, std::vector<long long int>)':
burza.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < kthDepth.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
burza.cpp:46:51: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |         if(dp(d+1, u.second)) return memo[d][mask]=true;
burza.cpp:48:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   48 |     if(mp.size()==0) return memo[d][mask]=true;
burza.cpp:49:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   49 |     return memo[d][mask]=false;

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 548 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -