Submission #457996

#	Time	Username	Problem	Language	Result	Execution time	Memory
457996		julian33	Political Development (BOI17_politicaldevelopment)	C++14	39 / 100	3068 ms	26524 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=5e4+5; //make sure this is right
const int mod=1e9+7;

/*
transform the directed graph to a bidirectional graph
an edge exists between a and b iff there is an edge a->b and b->a
binary search for the best k
start from the lowest node, only traverse to greater nodes that have degree >= k-1
*/

set<int> graph[mxN];
vector<int> cur;
int n,k;

bool dfs(int &s){
    if(sz(cur)==s)
        return 1;
    int at=cur.back();
    for(int i:graph[at]){
        if(i<=at || sz(graph[i])<s-1)
            continue;
        int bad=0;
        for(int &j:cur){
            if(!graph[i].count(j)){
                bad=1;
                break;
            }
        }
        if(bad)
            continue;
        cur.pb(i);
        if(dfs(s))
            return 1;
        cur.pop_back();
    }
    return 0;
}

bool check(int &s){
    for(int i=0;i<n;i++){
        if(sz(graph[i])<s-1)
            continue;
        cur={i};
        if(dfs(s))
            return 1;
    }
    return 0;
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    cin>>n>>k;
    for(int i=0;i<n;i++){
        int d; cin>>d;
        while(d--){
            int x; cin>>x;
            graph[i].insert(x);
        }
    }
    for(int i=0;i<n;i++){
        vector<int> rem;
        for(int j:graph[i]){
            if(!graph[j].count(i))
                rem.pb(j);
        }
        for(int &j:rem)
            graph[i].erase(j);
    }
    int l=1; int r=k;
    int ans=1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid; l=mid+1;
        } else{
            r=mid-1;
        }
    }
    cout<<ans<<"\n";
}

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