oj.uz

Submission #960759

# Submission time Handle Problem Language Result Execution time Memory
960759 2024-04-11T02:53:15 Z doducanh Burza (COCI16_burza) C++14
160 / 160
 37 ms 1536 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define fi first
#define se second
vector<int>a[405];
map<int,int>lost;
int max_cover[1<<20+7];
vector<vector<int>>cutoff;
vector<pair<int,int>>intervals;
vector<int>dep[405];
int n,k;
void process(int at,int prev,int depth)
{
    dep[depth].push_back(at);
    if(depth==k){
        lost[at]=lost.size();
        cutoff[at]={at};
        return;
    }
    for(int v:a[at])if(v!=prev){
        process(v,at,depth+1);
        cutoff[at].insert(cutoff[at].end(),cutoff[v].begin(),cutoff[v].end());
    }
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    cutoff.resize(n+1);
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    if(k*k>=n)return cout<<"DA",0;
    process(0,0,0);
    for(const vector<int>&cc:cutoff){
        if(cc.empty()){
            intervals.push_back({-1,-1});
        }
        else intervals.push_back({lost[cc.front()]+1,lost[cc.back()]+1});
    }
    max_cover[0]=0;
    for(int mask=1;mask<(1<<k);mask++){
        int &curr=max_cover[mask];
        for(int to_add=0;to_add<k;to_add++){
            if(((mask>>(to_add))&1)){
                int pre=max_cover[mask^(1<<to_add)];
                for(int v:dep[to_add+1]){
                    if(intervals[v].fi<=pre+1){
                        curr=max(curr,intervals[v].se);
                    }
                }
            }
        }
        if(max_cover[mask]==lost.size()){
            cout<<"DA";
            return 0;
        }
    }
    cout<<"NE";
    return 0;
}

Compilation message

burza.cpp:9:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    9 | int max_cover[1<<20+7];
      |                  ~~^~
burza.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main()
      | ^~~~
burza.cpp: In function 'int main()':
burza.cpp:61:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if(max_cover[mask]==lost.size()){
      |            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 34 ms 1340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1388 KB Output is correct
2 Correct 32 ms 1372 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 35 ms 1476 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1508 KB Output is correct
2 Correct 35 ms 1372 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 35 ms 1372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1368 KB Output is correct
2 Correct 34 ms 1372 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1364 KB Output is correct
2 Correct 30 ms 1480 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1420 KB Output is correct
2 Correct 35 ms 1460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 31 ms 1480 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 676 KB Output is correct
2 Correct 37 ms 1424 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 37 ms 1536 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1028 KB Output is correct
2 Correct 34 ms 1456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 14 ms 920 KB Output is correct
6 Correct 0 ms 348 KB Output is correct