Submission #169359

#	Time	Username	Problem	Language	Result	Execution time	Memory
169359		gabrielpessoa	Political Development (BOI17_politicaldevelopment)	C++14	16 / 100	3026 ms	12408 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

const int ms = 4e5+5;

vector<int> g[ms];
int cur[ms];
int z = 0;

main() {
  cin.tie(0); ios::sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  int maxS = 0;
  for (int i = 0; i < n; i++) {
    int d;
    cin >> d;
    maxS = max(maxS, d);
    g[i].resize(d);
    for(int j = 0; j < d; j++) {
      cin >> g[i][j];
    }
  }
  int ans = 1;
  if(maxS <= 10) {
    for(int i = 0; i < n; i++) {
      int t = g[i].size();
      for(int j = 0; j < (1 << t); j++) {
        vector<int> v = {i};
        bool isGood = true;
        for(int k = 0; k < t; k++) {
          if(j & (1 << k)) {
            if(g[i][k] < i) {
              isGood = false;
              break;
            }
            v.push_back(g[i][k]);
          }
        }
        if(!isGood) continue;
        ++z;
        for(int k : v) {
          cur[k] = z;
        }
        bool possible = true;
        for(int k : v) {
          int cnt = 0;
          for(int l : g[k]) if(cur[l] == z) cnt++;
          if(cnt != v.size() -1) possible = false;
        }
        if(possible) ans = max(ans, (int) v.size());
      }
    }
  } else if(n <= 5000 && k <= 3) {
    for(int i = 0; i < n; i++) {
      if(g[i].size() > 0) ans = max(ans, 2);
      set<int> s;
      for(int j : g[i]) {
        for(int k : g[j]) {
          if(s.count(k)) ans = max(ans, 3);
        }
        s.insert(j);
      }
    }
  } 
  cout << ans << '\n';
}

Compilation message (stderr)

politicaldevelopment.cpp:12:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           if(cnt != v.size() -1) possible = false;
              ~~~~^~~~~~~~~~~~~~

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