oj.uz

Submission #83305

# Submission time Handle Problem Language Result Execution time Memory
83305 2018-11-06T22:11:01 Z fredbr Alkemija (COCI18_alkemija) C++17
80 / 80
 80 ms 20052 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100100;

int ini[maxn];

vector<int> v[maxn*2];
int g[maxn*2];

int vis[maxn*2];

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

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {

		int a;
		cin >> a;

		ini[a] = 1;
	}

	int k;
	cin >> k;

	for (int i = 1; i <= k; i++) {

		int l, r;
		cin >> l >> r;

		g[n+i] = l;

		for (int j = 0; j < l; j++) {

			int a;
			cin >> a;

			v[a].push_back(n+i);
		}

		for (int j = 0; j < r; j++) {

			int a;
			cin >> a;

			v[n+i].push_back(a);
		}
	}

	for (int i = 1; i <= n; i++) {

		if (ini[i]) {

			g[i] = 0;
			vis[i] = 1;

		} else {

			g[i] = 1;
		}
	}

	vector<int> zero;

	for (int i = 1; i <= n; i++) if (g[i] == 0) zero.push_back(i);

	for (int i = 0; i < zero.size(); i++) {

		int at = zero[i];

		for (int u : v[at]) {

			if (vis[u]) continue;

			g[u]--;

			if (g[u] <= 0) {
				
				zero.push_back(u);
				vis[u] = 1;
			}
		}
	}

	vector<int> ans;

	for (int i : zero) {

		if (i <= n) ans.push_back(i);
	}

	sort(ans.begin(), ans.end());

	cout << ans.size() << "\n";
	for (int i : ans) cout << i << " ";
	cout << "\n";

	return 0;
}

Compilation message

alkemija.cpp: In function 'int main()':
alkemija.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < zero.size(); i++) {
                  ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5264 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5264 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5264 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5432 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7292 KB Output is correct
2 Correct 37 ms 8624 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11304 KB Output is correct
2 Correct 57 ms 13076 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15124 KB Output is correct
2 Correct 63 ms 15884 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 19196 KB Output is correct
2 Correct 70 ms 20052 KB Output is correct