oj.uz

Submission #244693

# Submission time Handle Problem Language Result Execution time Memory
244693 2020-07-04T15:33:32 Z TheLorax Political Development (BOI17_politicaldevelopment) C++11
0 / 100
 3000 ms 1024 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Execution timed out 3074 ms 768 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Execution timed out 3074 ms 768 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Execution timed out 3074 ms 768 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Execution timed out 3074 ms 768 KB Time limit exceeded
9 Halted 0 ms 0 KB -