Submission #1117571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117571		vjudge1	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	793 ms	27856 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
map<pair<int,int>,bool> edges;
int ans=1;
void backtrack(vector<int> &alive,vector<int> &v,int i){
    if(i==alive.size()){
        bool flag=true;
        for(int a=0;a<v.size();a++){
            for(int b=a+1;b<v.size();b++){
                flag&=(edges.find({min(v[a],v[b]),max(v[a],v[b])})!=edges.end());
                if(!flag){
                    break;
                }
            }
            if(!flag){
                break;
            }
        }
        if(flag){
            ans=max(ans,(long long)v.size());
        }
        return;
    }
    v.push_back(alive[i]);
    backtrack(alive,v,i+1);
    v.pop_back();
    backtrack(alive,v,i+1);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    set<pair<int,int>> se;
    int deg[n]={0};
    vector<vector<int>> graph(n);
    for(int i=0;i<n;i++){
        int d;
        cin >> d;
        for(int j=0;j<d;j++){
            int v;
            cin >> v;
            deg[i]++,deg[v]++;
            graph[i].push_back(v);
            edges[{min(i,v),max(i,v)}]=true;
        }
    }
    for(int i=0;i<n;i++){
        se.insert({deg[i],i});
    }
    bool del[n]={false};
    while(!se.empty()){
        int u=(*se.begin()).second;
        se.erase(se.begin());
        vector<int> alive;
        for(int v:graph[u]){
            if(!del[v]){
                alive.push_back(v);
            }
        }
        vector<int> temp;
        temp.push_back(u);
        backtrack(alive,temp,0);
        del[u]=true;
        for(int v:graph[u]){
            if(!del[v]){
                se.erase({deg[v],v});
                deg[v]--;
                se.insert({deg[v],v});
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void backtrack(std::vector<long long int>&, std::vector<long long int>&, long long int)':
politicaldevelopment.cpp:8:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     if(i==alive.size()){
      |        ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:10:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         for(int a=0;a<v.size();a++){
      |                     ~^~~~~~~~~
politicaldevelopment.cpp:11:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |             for(int b=a+1;b<v.size();b++){
      |                           ~^~~~~~~~~

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