oj.uz

Submission #94950

# Submission time Handle Problem Language Result Execution time Memory
94950 2019-01-25T12:54:37 Z noclever Conspiracy (POI11_kon) C++14
100 / 100
 2341 ms 84984 KB 
#include <vector>
#include <iostream>
#include <set>
#include <bitset>
#include <algorithm>
using namespace std;
 
int n;
vector< vector<short> > g, tg;
vector< bitset<5001> > mat;
vector<int> was, topoSort, scc;
vector<int> index, lowlink, s;
int cur = 1, gi = 1;
vector<int> as;
vector<int> st;
vector<short> x[2];
int cnt[2][2];
 
void add_edge(int u, int v) {
	g[u].push_back(v);
}
 
void strongconnect(int u) {
	index[u] = gi;
	lowlink[u] = gi;
	gi++;
	
	s.push_back(u);
	was[u] = 2;
 
	for (auto& v : g[u]) {
		if (!was[v]) {
			strongconnect(v);
			lowlink[u] = min(lowlink[v], lowlink[u]);
		}
		else if (was[v] == 2) {
			lowlink[u] = min(lowlink[u], index[v]);
		}
	}
 
	if (lowlink[u] == index[u]) {
		while (true) {
			int w = s.back();
			s.pop_back();
			scc[w] = cur;
			if (w == u) break;
		} 
		cur++;
	}
 
	was[u] = 1;
 
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	mat.assign(n + 1, bitset<5001>());
	g.resize(2 * n + 1);
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		while (k--) {
			int a;
			cin >> a;
			mat[a][i] = mat[i][a] = 1;
		}
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (mat[i][j]) {
				add_edge(i, j + n);
				add_edge(j, i + n);
			}
			else {
				add_edge(i + n, j);
				add_edge(j + n, i);
			}
		}
	}
 
	was.assign(2 * n + 1, 0);
	scc.assign(2 * n + 1, -1);
 
	index.assign(2 * n + 1, 0);
	lowlink.assign(2 * n + 1, 0);
 
	for (int i = 1; i <= 2 * n; i++) {
		if (!was[i]) {
			strongconnect(i);
		}
	}	
	
	as.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		if (scc[i] == scc[i + n]) {
			cout << 0 << '\n';
			return 0;
		}
		as[i] = scc[i] < scc[i + n];
	}
	int ans = 1;
	int sup = 0, con = 0;
	for (int i = 1; i <= n; i++) {
		sup += 1 - as[i];
		con += as[i];
		x[1 - as[i]].push_back(i);
	}
 
	if ((sup == 0) || (con == 0)) {
		ans = 0;
	}
 
	st.resize(n + 1);
 
	for (auto& u : x[0]) {
		for (auto& v : x[1]) {
			int idx = mat[u][v] ? v : u;
			int idx2 = mat[u][v] ? u : v;
			if (st[idx] > 0) {
				st[idx] = -1;
			} else if (st[idx] == 0) {
				st[idx] = idx2;
			}
		}
	}
 
	for (int i = 1; i <= n; i++) {
		if (st[i] == 0) {
			if ((as[i]) && (con > 1)) ans++;
			if ((!as[i]) && (sup > 1)) ans++;
		}
	}
	
	for (int i = 0; i < 2; i++) {
		for (auto& u : x[i]) {
			if (st[u] == 0) {
				cnt[i][0]++;
			}
			else if (st[u] > 0) {
				cnt[i][1]++;
			}
		}
	}
 
	ans += cnt[0][0] * cnt[1][1] + cnt[0][1] * cnt[1][0];
	
 
 
	cout << ans << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 3 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 4 ms 632 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7364 KB Output is correct
2 Correct 76 ms 9320 KB Output is correct
3 Correct 252 ms 14868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8696 KB Output is correct
2 Correct 123 ms 12452 KB Output is correct
3 Correct 372 ms 15944 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 26784 KB Output is correct
2 Correct 267 ms 28568 KB Output is correct
3 Correct 617 ms 28536 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 41976 KB Output is correct
2 Correct 656 ms 46968 KB Output is correct
3 Correct 1420 ms 41092 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1329 ms 82456 KB Output is correct
2 Correct 1092 ms 84984 KB Output is correct
3 Correct 2220 ms 80516 KB Output is correct
4 Correct 2341 ms 81400 KB Output is correct
5 Correct 467 ms 77560 KB Output is correct