제출 #1358290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358290		AgentPengin	Uzastopni (COCI15_uzastopni)	C++20	112 / 160	9 ms	17664 KiB

uzastopni

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

const int MAXN = 10005;
const int MAXV = 101;

int n;
int v[MAXN];
vector<int> adj[MAXN];
bitset<MAXV> dp[MAXN][MAXV]; 
// dp[u][L][R] = 1 nghĩa là cây con u có thể tạo đoạn [L, R]

void dfs(int u) {
    // Khởi tạo: Mỗi đỉnh tự tạo thành đoạn [v[u], v[u]]
    dp[u][v[u]].set(v[u]);

    for (int child : adj[u]) {
        dfs(child);

        // Thử ghép các đoạn của con vào cha
        // Ta cần duyệt mọi L_u có thể để cập nhật
        for (int lu = 1; lu < MAXV; ++lu) {
            if (dp[u][lu].none()) continue;

            // Tìm các đoạn của con có thể nối vào bên phải của u: [lu, ru] + [ru+1, rv]
            // Ru là vị trí bit cao nhất đang bật của dp[u][lu]
            for (int ru = lu; ru < MAXV; ++ru) {
                if (dp[u][lu].test(ru)) {
                    if (ru + 1 < MAXV) {
                        // Nếu con có đoạn bắt đầu từ ru + 1, ta OR toàn bộ bitset đó vào
                        // Điều này tương đương với việc mở rộng ru thành các rv của con
                        dp[u][lu] |= dp[child][ru + 1];
                    }
                }
            }

            // Tìm các đoạn của con có thể nối vào bên trái của u: [lv, lu-1] + [lu, ru]
            for (int lv = 1; lv < lu; ++lv) {
                if (dp[child][lv].test(lu - 1)) {
                    // Nếu con có đoạn kết thúc tại lu-1, toàn bộ ru hiện tại của u
                    // đều có thể bắt đầu từ lv
                    dp[u][lv] |= dp[u][lu];
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) cin >> v[i];

    for (int i = 0; i < n - 1; ++i) {
        int u, v_edge;
        cin >> u >> v_edge;
        adj[u].push_back(v_edge);
    }

    dfs(1);

    // Kết quả bài toán là số lượng đoạn [L, R] hợp lệ tại gốc 1
    int total_ranges = 0;
    for (int l = 1; l < MAXV; ++l) {
        total_ranges += dp[1][l].count();
    }

    cout << total_ranges << endl;

    return 0;
}

• 서브태스크 1: 112 / 160