oj.uz

Submission #310650

# Submission time Handle Problem Language Result Execution time Memory
310650 2020-10-07T14:35:18 Z MrDomino Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 59 ms 2176 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=50000+7;
int n;
int k;
int sol;
vector<int> g[N];
set<pair<int,int>> s;

void del(int x)
{
        for (auto &i : g[x])
        {
                vector<int> gnew_i;
                for (auto &y : g[i])
                {
                        if (y!=x)
                                gnew_i.push_back(y);
                }
                s.erase({(int) g[i].size(),i});
                s.insert({(int) g[i].size()-1,i});
                g[i]=gnew_i;
        }
        g[x].clear();
}

vector<int> operator & (vector<int> a, vector<int> b)
{
        vector<int> c;
        int i=0,j=0;
        while (i<(int) a.size()&&j<(int) b.size())
        {
                if (a[i]<b[j])
                {
                        i++;
                        continue;
                }
                if (b[j]<a[i])
                {
                        j++;
                        continue;
                }
                c.push_back(a[i]);
                i++;
                j++;
        }
        return c;
}

vector<int> nodes;
vector<int> good;

void bkt()
{
        if ((int) good.size()+(int)nodes.size()<=sol)
                return;
        if ((int)nodes.size()>sol)
                sol=(int)nodes.size();
        vector<int> init=good;
        for (auto &x : good)
        {
                if ((int) nodes.size()>1&&x<nodes.back())
                        continue;
                good=good&g[x];
                nodes.push_back(x);
                bkt();
                nodes.pop_back();
                good=init;
        }
}

int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);


        cin>>n>>k;
        for (int i=0;i<n;i++)
        {
                int l;
                cin>>l;
                for (int j=1;j<=l;j++)
                {
                        int x;
                        cin>>x;
                        g[i].push_back(x);
                }
                sort(g[i].begin(),g[i].end());
                s.insert({(int)g[i].size(),i});
        }
        while (!s.empty())
        {
                auto it=*s.begin();
                s.erase(it);
                int node=it.second;
                good=g[node];
                nodes={node};
                bkt();
                del(node);
        }
        cout<<sol<<"\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 7 ms 1920 KB Output is correct
4 Correct 59 ms 1920 KB Output is correct
5 Correct 56 ms 2004 KB Output is correct
6 Correct 9 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 3 ms 1792 KB Output is correct
9 Correct 1 ms 1536 KB Output is correct
10 Correct 3 ms 1792 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 7 ms 1920 KB Output is correct
4 Correct 59 ms 1920 KB Output is correct
5 Correct 56 ms 2004 KB Output is correct
6 Correct 9 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 3 ms 1792 KB Output is correct
9 Correct 1 ms 1536 KB Output is correct
10 Correct 3 ms 1792 KB Output is correct
11 Correct 58 ms 1920 KB Output is correct
12 Correct 59 ms 1920 KB Output is correct
13 Incorrect 3 ms 2176 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1792 KB Output is correct
2 Incorrect 1 ms 1536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 7 ms 1920 KB Output is correct
4 Correct 59 ms 1920 KB Output is correct
5 Correct 56 ms 2004 KB Output is correct
6 Correct 9 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 3 ms 1792 KB Output is correct
9 Correct 1 ms 1536 KB Output is correct
10 Correct 3 ms 1792 KB Output is correct
11 Correct 58 ms 1920 KB Output is correct
12 Correct 59 ms 1920 KB Output is correct
13 Incorrect 3 ms 2176 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 7 ms 1920 KB Output is correct
4 Correct 59 ms 1920 KB Output is correct
5 Correct 56 ms 2004 KB Output is correct
6 Correct 9 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 3 ms 1792 KB Output is correct
9 Correct 1 ms 1536 KB Output is correct
10 Correct 3 ms 1792 KB Output is correct
11 Correct 58 ms 1920 KB Output is correct
12 Correct 59 ms 1920 KB Output is correct
13 Incorrect 3 ms 2176 KB Output isn't correct
14 Halted 0 ms 0 KB -