Submission #1306258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306258		Robert_junior	Political Development (BOI17_politicaldevelopment)	C++20	77 / 100	971 ms	323296 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
#define bt bitset<50010>
const int N = 50010, K = 1610;
const int mod = 998244353;
vector<int>g[N], gg[N];
bt b[N];
int ans = 1;
vector<int>V;
bool used[N];
int n, k;
auto start_time = std::chrono::high_resolution_clock::now();
clock_t start_ticks;
void dfs(int v){
    used[v] = 1;
    V.pb(v);
    ans = max(ans, (int)(V.size()));
    double elapsed = (double)(clock() - start_ticks) / CLOCKS_PER_SEC;
    if (elapsed > 0.95) {
        return;
    }
    for(auto to : g[v]){
        if(to < v) continue;
        bool ok = 1;
        for(auto it : V){
            if(!b[it][to]){
                ok = 0;
                break;
            }
        }
        if(ok){
            dfs(to);
        }
    }
    used[v] = 0;
    V.pop_back();
}
bool cmp(int x, int y){
    return g[x].size() < g[y].size();
}
int ord[N];
void solve(){
	cin>>n>>k;
	for(int i = 1; i <= n; i++){
		int m;
		cin>>m;
		for(int j = 1; j <= m; j++){
			int x;
			cin>>x;
			x++;
			gg[i].pb(x);
		}
	}
	for(int i = 1; i <= n; i++){
	    for(auto to : gg[i]){
	        for(auto it : gg[to]){
	            if(it == i){
    	            g[i].pb(to);
    	            b[i][to] = 1;
	            }
	        }
	    }
	    sort(all(g[i]), cmp);
	}
	for(int i = 1; i <= n; i++){
	    ord[i] = i;
	}
	sort(ord + 1, ord + n + 1, cmp);
	for(int i = 1; i <= n; i++){
	    dfs(ord[i]);
	}
	cout<<ans;
}
main(){
    start_ticks = clock();
	ios_base :: sync_with_stdio(false); 
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

politicaldevelopment.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main(){
      | ^~~~

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