Submission #971525

#TimeUsernameProblemLanguageResultExecution timeMemory
971525gutzzyPolitical Development (BOI17_politicaldevelopment)C++17
54 / 100
3085 ms9896 KiB
#include <bits/stdc++.h>
using namespace std;
//#define int unsigned short
int n,k,d,a;
int ans = 0;
vector<vector<int>> ady;
vector<vector<int>> adyd;

void dfs(int nodo, int sz, vector<int> c){
    ans = max(ans,sz);
    for(int x:adyd[nodo]) c[x]++;
    for(int x:adyd[nodo]){
        if(c[x]>=sz) dfs(x,sz+1,c); // todos los nodos "anteriores" están conectados
    }
    for(int x:adyd[nodo]) c[x]--;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    ady = vector<vector<int>>(n,vector<int>());
    adyd = vector<vector<int>>(n,vector<int>());
    vector<int> deg(n);
    for(int i=0;i<n;i++){
        cin >> d;
        deg[i] = d;
        for(int j=0;j<d;j++){
            cin >> a;
            ady[i].push_back(a);
        }
    }
    
    // paso a dirigido
    for(int i=0;i<n;i++){
        for(int vec:ady[i]){
            if(deg[i]<deg[vec] or (deg[i]==deg[vec] and i<vec)) adyd[i].push_back(vec);
        }
    }
    
    vector<int> c(n,0);
    for(int i=0;i<n;i++){
        dfs(i, 1, c);
    }
    
    cout << ans << endl;   
}
#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...