Submission #1103721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103721		ortsac	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1505 ms	4424 KiB

politicaldevelopment

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
 
const int MAXN = 5e4 + 10;
int n, k;

vector<int> adj[MAXN];
 
void merge(vector<int>& v1, vector<int>& v2, vector<int>& res) {
    int n = v1.size(), m = v2.size();
    int p1 = 0, p2 = 0;
    while ((p1 < n) && (p2 < m)) {
        if (v1[p1] == v2[p2]) {
            res.push_back(v1[p1]);
            p1++;
            p2++;
            continue;
        }
        if (v1[p1] > v2[p2]) p1++;
        else p2++;
    }
}
 
int best(vector<int> pos) {
    int mx = 0;
    while (!pos.empty()) {
        auto u = pos.back();
        pos.pop_back();
        vector<int> nxt;
        merge(pos, adj[u], nxt);
        mx = max(mx, 1 + best(nxt));
    }
    return mx;
}
 
int32_t main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        while (x--) {
            int v;
            cin >> v;
            if (v > i) adj[i].push_back(v);
        }
        sort(adj[i].begin(), adj[i].end(), greater<int>());
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, best(adj[i]) + 1);
        if (ans == k) break;
    }
    cout << ans << "\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23