Submission #244693

#	Time	Username	Problem	Language	Result	Execution time	Memory
244693		TheLorax	Political Development (BOI17_politicaldevelopment)	C++11	0 / 100	3078 ms	1024 KiB

politicaldevelopment

#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;

int n;
std::vector<std::vector<int> > e;

void rek(std::vector<int> &ou, int k, int ki=0){
  if(ki==k){
    printf("%d\n", k);
    exit(0);
  }
  for(int i=0; i<n; i++)
    if(ou[i]==ki){
      for(int x: e[i])
        ou[x]++;
      rek(ou, k, ki+1);
      for(int x: e[i])
        ou[x]--;
    }
  return;
}

void trycli(int k){
  std::vector<int> ou(n);
  set<ii> s;
  for(int i=0; i<n; i++){
    int d=SZ(e[i]);
    s.insert({d,i});
    ou[i]=d;
  }
  auto x=s.begin();
  while (x!=s.end() && x->F<k-1) {
    ou[x->S]=-1;
    for(auto y: e[x->S]){
      if(ou[y]<0)
        continue;
      s.erase({ou[y], y});
      ou[y]--;
      s.erase({ou[y], y});
    }
    x=s.begin();
  }
  if(x==s.end())
    return;
  if(SZ(s)==k){
    printf("%d\n", k);
    exit(0);
  }
  for(int i=0; i<n; i++){
    if(ou[i]>=0)
      ou[i]=0;
    else
      ou[i]=INT_MIN/2;
  }
  rek(ou, k);
}

int main(){
  int k;
  scanf("%d %d", &n, &k);
  e.resize(n);
  for(int i=0; i<n; i++){
    int d; scanf("%d", &d);
    e[i].resize(d);
    for(int j=0; j<d; j++)
      scanf("%d", &e[i][j]);
  }
  for(int i=k; i>1; i--)
    trycli(i);
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int d; scanf("%d", &d);
            ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:85:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &e[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~

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