Submission #128724

#	Time	Username	Problem	Language	Result	Execution time	Memory
128724		SamAnd	Political Development (BOI17_politicaldevelopment)	C++17	39 / 100	3025 ms	8164 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
const int N = 50004;

int n, k;
vector<int> a[N];

int ans;

vector<int> b;

bool c[N];
vector<int> v;

void rec(int i)
{
    ans = max(ans, (int)v.size());
    if (i == b.size())
    {
        return;
    }
    rec(i + 1);
    int q = 0;
    for (int j = 0; j < a[b[i]].size(); ++j)
    {
        int h = a[b[i]][j];
        if (c[h])
            ++q;
    }
    if (q != v.size())
        return;
    c[b[i]] = true;
    v.push_back(b[i]);
    rec(i + 1);
    v.pop_back();
    c[b[i]] = false;
}

void solv3()
{
    for (int i = 1; i <= n; ++i)
    {
        b.clear();
        for (int j = 0; j < a[i].size(); ++j)
            b.push_back(a[i][j]);
        c[i] = true;
        v.push_back(i);
        rec(0);
        v.pop_back();
        c[i] = false;
    }
    cout << ans << endl;
}

void rec1(int i)
{
    ans = max(ans, (int)v.size());
    if (i == b.size())
    {
        return;
    }
    rec1(i + 1);
    for (int j = 0; j < v.size(); ++j)
    {
        if (!binary_search(a[b[i]].begin(), a[b[i]].end(), v[j]))
            return;
    }
    c[b[i]] = true;
    v.push_back(b[i]);
    rec1(i + 1);
    v.pop_back();
    c[b[i]] = false;
}

void solv5()
{
    for (int i = 1; i <= n; ++i)
    {
        b.clear();
        for (int j = 0; j < a[i].size(); ++j)
            b.push_back(a[i][j]);
        c[i] = true;
        v.push_back(i);
        rec1(0);
        v.pop_back();
        c[i] = false;
    }
    cout << ans << endl;
}

int main()
{
    scanf("%d%d", &n, &k);
    int maxu = 0;
    for (int i = 0; i < n; ++i)
    {
        int s;
        scanf("%d", &s);
        maxu = max(maxu, s);
        while (s--)
        {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
        }
        sort(a[i].begin(), a[i].end());
    }
    solv5();
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void rec(int)':
politicaldevelopment.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i == b.size())
         ~~^~~~~~~~~~~
politicaldevelopment.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < a[b[i]].size(); ++j)
                     ~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:30:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (q != v.size())
         ~~^~~~~~~~~~~
politicaldevelopment.cpp: In function 'void solv3()':
politicaldevelopment.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < a[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void rec1(int)':
politicaldevelopment.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i == b.size())
         ~~^~~~~~~~~~~
politicaldevelopment.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < v.size(); ++j)
                     ~~^~~~~~~~~~
politicaldevelopment.cpp: In function 'void solv5()':
politicaldevelopment.cpp:80:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < a[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &s);
         ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

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