oj.uz

Submission #918845

# Submission time Handle Problem Language Result Execution time Memory
918845 2024-01-30T14:20:34 Z Ludissey Burza (COCI16_burza) C++14
0 / 160
 1000 ms 12884 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 = 0; 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];
    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];
        int c=comf(kthDepth[i]);
        int pw=(1<<(kthDepth[i]-(c*50)));
        empty[c]=empty[comf(kthDepth[i])]+pw;
        mp[u]=empty;
    }
    for (auto u : mp)
    {
        vector<int> newMASK(8);
        for (int i = 0; i < 8; i++) newMASK[i]=mask[i]|u.second[i];
        
        if(d==k) {
            if(compMask(newMASK, optimal)) return true;
        }
        else if(dp(d+1, newMASK)) 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(1, 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:31: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]
   31 |     for (int i = 0; i < kthDepth.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
burza.cpp:53:55: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   53 |         else if(dp(d+1, newMASK)) return memo[d][mask]=true;
burza.cpp:55:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   55 |     if(mp.size()==0) return memo[d][mask]=true;
burza.cpp:56:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   56 |     return memo[d][mask]=false;

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 9036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 6748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 9444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 12884 KB Time limit exceeded
2 Halted 0 ms 0 KB -