Submission #1083587

#TimeUsernameProblemLanguageResultExecution timeMemory
1083587_8_8_Political Development (BOI17_politicaldevelopment)C++17
100 / 100
726 ms34796 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...