Submission #1239145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239145		lambd47	Robots (APIO13_robots)	C++20	0 / 100	2 ms	320 KiB

robots

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n,k;cin>>n>>k;
    vector<set<int>> adj(n);
    L(i,0,n-1){
        int x;cin>>x;
        L(j,0,x-1){
            int a;cin>>a;
            adj[i].insert(a);
        }
    }

    set<pair<int,int>> ord;
    L(i,0,n-1)ord.insert({sz(adj[i]),i});



    vector<int> at;
    int x;
    vector<int> st;
    auto solv=[&](auto&& self,int id)->int{
        if(id==x)return 0;
        int ret=self(self,id+1);
        for(auto a:st){
            if(adj[id].find(a)==adj[id].end())return ret;
        }
        st.push_back(at[id]);
        ret=max(ret,1+self(self,id+1));
        st.pop_back();
        return ret;
    };
    int resp=0;
    while(!ord.empty()){
        auto pt=ord.begin();
        auto [tam,id]=*pt;
        ord.erase(pt);
        at.clear();
        for(auto a:adj[id]){
            at.push_back(a);
        }
        for(auto a: at){
            ord.erase({sz(adj[a]),a});
            adj[a].erase(id);
            ord.insert({sz(adj[a]),a});
        }
        x=sz(at);
        resp=max(resp,1+solv(solv,0));
    }
    cout<<resp;
}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40