oj.uz

Submission #472587

# Submission time Handle Problem Language Result Execution time Memory
472587 2021-09-13T18:47:09 Z Hamed5001 Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 5 ms 1612 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 5e4;
vector<int> adj[mxN];
map<int, int> freq;
bool vis[mxN];
int N, K;


bool can(int k) {
	vector<pair<int, int>> freq(N, pair<int, int>(0, -1));
	for (int i = 0; i < N; i++) {
		if (adj[i].size()+1 < k)
			continue;
		for (int msk = 0; msk < (1<<adj[i].size()); msk++) {
			if (__builtin_popcount(msk) != k-1)
				continue;
			for (int j = 0; j < adj[i].size(); j++) {
				if ((1<<j) & msk) {
					for (int k = 0; k < adj[adj[i][j]].size(); k++) {
						if (freq[adj[adj[i][j]][k]].second != i)
							freq[adj[adj[i][j]][k]].second = i, freq[adj[adj[i][j]][k]].first = 0;
						freq[adj[adj[i][j]][k]].first++;
					}
				}
  			}
		}
		if (freq[i].first != k-1)
			continue;
		for (auto it : adj[i])
			if (freq[it].first != k-1)
				continue;
		return 1;
	}
	return 0;
}

void solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int D;
		cin >> D;
		while(D--) {
			int v;
			cin >> v;
			adj[i].push_back(v);
		}
	}
	for (int i = K; i >= 2; i--)
		if (can(i))
			return void(cout << i);
	cout << 1;
}

int main() {

	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message

politicaldevelopment.cpp: In function 'bool can(int)':
politicaldevelopment.cpp:16:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |   if (adj[i].size()+1 < k)
      |       ~~~~~~~~~~~~~~~~^~~
politicaldevelopment.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for (int j = 0; j < adj[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |      for (int k = 0; k < adj[adj[i][j]].size(); k++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 5 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 5 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Incorrect 1 ms 1484 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Incorrect 1 ms 1484 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 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 5 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Incorrect 1 ms 1484 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 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 5 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Incorrect 1 ms 1484 KB Output isn't correct
14 Halted 0 ms 0 KB -