Submission #1096029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096029		frankmauer1812	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	169 ms	66896 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;

#define sonic ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define IO(main) if(fopen(main".inp", "r")){freopen(main".inp", "r", stdin);freopen(main".out", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define el cout << "\n"
#define SZ(x) (x).size()
#define ALL(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & (1LL))
#define MASK(x) ((1LL) << (x))
#define FOR(i, a, b) for(int (i) = (a), _b = (b); (i) <= _b; (i)++)
#define FORD(i, a, b) for(int (i) = (a), _b = (b); (i) >= _b; (i)--)

const int N = MASK(20) + 5;
const int mod = 1e9 + 7;
const ll INF = 1e9 + 7;

template<class X, class Y> bool maximize(X &x, Y y){if(x < y){x = y; return true;} return false;}
template<class X, class Y> bool minimize(X &x, Y y){if(x > y){x = y; return true;} return false;}
void add(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub(int &x, int y){x -= y; if(x < 0) x += mod;}
int mul(int x, int y) {return 1LL * x * y % mod;}
int calPw(int x, int y){
    int ans = 1;
    while(y){
        if(y & 1) ans = 1LL * ans * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return ans;
}
///Deruck Phung - Luong The Vinh High School For The Gifted
int n, d;
vector<int> adj[N];
///Code
namespace sub1{
    bool check(){
        return n <= 20;
    }
    pii dis[N][2];

    void Solve(){
        int Ans = 0;
        for(int mask = 0; mask < MASK(n); mask++){
            for(int i = 1; i <= n; i++)
                dis[i][0] = dis[i][1] = {-1, -1};
            queue<pii> qu;
            for(int i = 1; i <= n; i++) if(BIT(mask, i - 1)){
                dis[i][0] = {0, i};
                qu.push({i, 0});
            }
            while(qu.size()){
                int u = qu.front().fi;
                int type = qu.front().se;
                qu.pop();

                for(int v : adj[u]){
                    if(dis[v][0].fi == -1){
                        dis[v][0] = dis[u][type];
                        dis[v][0].fi++;
                        qu.push({v, 0});
                    }
                    else if(dis[v][1].fi == -1 && dis[u][type].se != dis[v][0].se){
                        dis[v][1] = dis[u][type];
                        dis[v][1].fi++;
                        qu.push({v, 1});
                    }
                }
            }
            bool oke = true;
            for(int i = 1; i <= n; i++) if(BIT(mask, i - 1)){
                if(dis[i][1].fi > 0 && dis[i][1].fi < d)
                    oke = false;
            }



            if(oke)
                Ans = max(Ans, __builtin_popcount(mask));
        }
        cout << Ans;
    }
}

namespace sub2{
    bool check(){
        return n <= 5000;
    }

    int mx[N];
    vector<int> dp[N];

    vector<int> Merge(vector<int> A, vector<int> B){
        vector<int> C;
        C.resize(min(d, max((int) A.size(), (int) B.size() + 1)), 0);
        for(int i = 0; i < A.size(); i++){
            for(int j = max(0, d - i - 1); j < B.size(); j++){
                C[min(i, j + 1)] = max(C[min(i, j + 1)], A[i] + B[j]);
            }
        }

        for(int i = C.size() - 1; i >= 0; i--){
            if(i < C.size() - 1)
                C[i] = max(C[i], C[i + 1]);
            if(i < A.size())
                C[i] = max(C[i], A[i]);
            if(i > 0 && i <= B.size())
                C[i] = max(C[i], B[i - 1]);
        }
        return C;
    }

    void dfs(int u, int p){
        dp[u].push_back(1);
        for(int v : adj[u]) if(v != p){
            dfs(v, u);

            dp[u] = Merge(dp[u], dp[v]);
        }
    }

    void Solve(){
        dfs(1, 1);

        int Ans = 0;
        for(int i = 0; i < dp[1].size(); i++)
            Ans = max(Ans, dp[1][i]);
        cout << Ans;
    }
}

namespace sub3{
    int f[N], g[N], cnt[N];
    void dfs(int u, int p){
        ///g[u]: thằng chưa được lấy trong cây con gốc u, có dist tới đỉnh u là g[u]
        ///Khi đó, với mỗi u, ta sẽ tìm cách lấy g[v] sao cho mỗi thằng >= d / 2
        ///Vậy khoảng cách của mỗi thằng luôn đảm bảo >= d / 2
        ///Ngoài ra, giả sử có 2 đỉnh là con của v, vậy 1 là nó sẽ lấy tại v
        ///2 là dist của 2 thằng < d, suy ra mỗi thằng v chỉ lấy 1 thằng.
        ///Để tìm được nhiều nhất -> g[u] luôn lớn nhất.

        ///f[u]: min dist từ thằng được chọn đến u
        ///cnt[u]: chọn trong cây con gốc u nhưng k chọn thằng u

        f[u] = 1e9 + 7;
        g[u] = -1;

        for(int v : adj[u]) if(v != p){
            dfs(v, u);
            cnt[u] += cnt[v];

            f[u] = min(f[u], f[v] + 1);
            ///Có thể lấy thằng v

            if(g[v] != -1){
                if(2 * (g[v] + 1) >= d){
                    f[u] = min(f[u], g[v] + 1);
                    cnt[u]++;
                }
                else
                    g[u] = max(g[u], g[v] + 1);
            }

        }

        ///Nếu khoảng cách của g[u] (thằng v cây con u chưa được lấy lớn nhất)
        ///và f[u] (thằng gần u nhất đã được chọn) < d thì coi như ta k thể lấy
        ///thằng đang được lưu ở g[u]

        if(g[u] + f[u] < d) g[u] = -1;
        if(g[u] == -1 && f[u] >= d) g[u] = 0;
    //    cout << u << " " << cnt[u] << " " << g[u] << "\n";
    }

    void Solve(){
        dfs(1, 1);
        cout << cnt[1] + (g[1] >= 0);
    }
}

void Solve(){

}

void Read(){
    cin >> n >> d;
    for(int i = 2; i <= n; i++){
        int x;
        cin >> x;
        ++x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }

    if(sub1::check()) sub1::Solve();
    else if(sub2::check()) sub2::Solve();
    else sub3::Solve();
}

int main(){
    sonic;
    IO("main");
    int TEST = 1;

    while(TEST--){
        Read();
        Solve();
    }
}

Compilation message (stderr)

catinatree.cpp: In function 'std::vector<int> sub2::Merge(std::vector<int>, std::vector<int>)':
catinatree.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i = 0; i < A.size(); i++){
      |                        ~~^~~~~~~~~~
catinatree.cpp:105:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for(int j = max(0, d - i - 1); j < B.size(); j++){
      |                                            ~~^~~~~~~~~~
catinatree.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             if(i < C.size() - 1)
      |                ~~^~~~~~~~~~~~~~
catinatree.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             if(i < A.size())
      |                ~~^~~~~~~~~~
catinatree.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             if(i > 0 && i <= B.size())
      |                         ~~^~~~~~~~~~~
catinatree.cpp: In function 'void sub2::Solve()':
catinatree.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int i = 0; i < dp[1].size(); i++)
      |                        ~~^~~~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:5:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define IO(main) if(fopen(main".inp", "r")){freopen(main".inp", "r", stdin);freopen(main".out", "w", stdout);}
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:210:5: note: in expansion of macro 'IO'
  210 |     IO("main");
      |     ^~
catinatree.cpp:5:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define IO(main) if(fopen(main".inp", "r")){freopen(main".inp", "r", stdin);freopen(main".out", "w", stdout);}
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:210:5: note: in expansion of macro 'IO'
  210 |     IO("main");
      |     ^~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49