Submission #971525

#	Time	Username	Problem	Language	Result	Execution time	Memory
971525		gutzzy	Political Development (BOI17_politicaldevelopment)	C++17	54 / 100	3085 ms	9896 KiB

politicaldevelopment

#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;   
}

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