Submission #1083587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083587		_8_8_	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	726 ms	34796 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 5e4 + 12, MOD = (int)1e9 + 7;

int n, k, timer = 0;
vector<int> g[N], vis[N];
map<vector<int>,int> mem;
int calc(vector<int> &x, int tim) {
    if(x.empty()) return 0;
    if(mem.count(x)) return mem[x];
    for(int i:x) {
        vis[i].push_back(tim);
    }
    int ret = 0;
    for(int i:x) {
        vector<int> nv;
        for(int to:g[i]) {
            if(!vis[to].empty() && vis[to].back() == tim) {
                nv.push_back(to);
            }
        }
        ret = max(ret,1 + calc(nv, tim + 1));
    }
    for(int i:x) {
        vis[i].pop_back();
    }
    return mem[x] = ret;
}
void test() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        int d;
        cin >> d;
        for(int j = 0; j < d; j++) {
            int x;
            cin >> x;
            ++x;
            g[x].push_back(i);
            // cout << x << ' ' << d << '\n';
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) {
        res = max(res, 1 + calc(g[i], 1));
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1; 
    // cin >> t;
    while(t--) 
        test();

    return 0;
}

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