Bài "The Number of Imposters" trên codeforces

[Circuit]

Lại là em đây : D. Không hiểu test case 23 chứa gì mà lại không cho code em pass. Mò đủ input rồi vẫn không ra.

Problem - 1594D - Codeforces

Code của em:

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
 
using namespace std;
 
#define ll long long int
 
const int IMPOSTER = 1;
const int CREWMATE = 0;
 
struct Edge
{
	int id;
	int comment_type;
 
	bool operator <(const Edge& e) const
	{
		if (id != e.id) return id < e.id;
		else return comment_type < e.comment_type;
	}
};
 
vector<set<Edge>> List;
map<pair<int, int>, bool> visited;
vector<bool> node_visited;
set<int> team[2];
int n, team_cnt[2];
 
bool dfs(int id, int team_id)
{
	node_visited[id] = true;
	int t_id;
 
	for (Edge e : List[id])
	{
		int Min = min(e.id, id), Max = max(e.id, id);
 
		if (!visited[{Min, Max + n * e.comment_type}])
		{
			visited[{Min, Max + n * e.comment_type}] = true;
 
			if (e.comment_type == IMPOSTER) t_id = 1 ^ team_id;
			else t_id = team_id;
 
			if (team[1 ^ t_id].find(e.id) != team[1 ^ t_id].end()) return false;
 
			team[t_id].insert(e.id);
			team_cnt[t_id]++;
			if (!dfs(e.id, t_id)) return false;
		}
 
	}
 
	return true;
}
 
int main()
{
	int num, m, u, v, _type, ans;
	bool possible;
 
	cin >> num;
 
	for (int i = 0; i < num; i++)
	{
		cin >> n >> m;
		string s;
 
		List.resize(n + 1); node_visited.resize(n + 1);
 
		for (int j = 0; j < m; j++)
		{
			cin >> u >> v >> s;
 
			if (s == "imposter") _type = IMPOSTER;
			else _type = CREWMATE;
 
			List[u].insert({ v, _type });
			List[v].insert({ u, _type });
		}
 
		possible = true; ans = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!node_visited[j])
			{
				team_cnt[0] = 1; team_cnt[1] = 0;
 
				team[0].insert(j);
				if (dfs(j, 0) == false)
				{
					possible = false;
					break;
				}
 
				ans += max(team_cnt[0], team_cnt[1]);
			}
		}
 
		if (!possible) cout << "-1" << endl;
		else cout << ans << endl;
 
		List.clear(); visited.clear(); node_visited.clear();
		team[0].clear(); team[1].clear();
	}
	return 0;
}

Em có liếc ké gợi ý 1 tí. Nếu ta có A nói B rằng B là imposter thì A, B không thể cùng danh xưng(A imposter thì B là crewmate và ngược lại). Còn nếu A nói B rằng B là crewmate thì A, B luôn cùng danh xưng. Cho nên ý tưởng phần code của em là: Ta sẽ có 2 nhóm cho từng connected component, 2 nhóm này là độc lập đối với mỗi connected component. Tạo đồ thị trong đó các cạnh phân biệt bằng 2 node nó nối và “kiểu comment”. Sau đó, dfs từng connected component theo cạnh và xét coi nhóm nào nhiều thành viên hơn thì gán danh xưng “Imposter” cho tất cả và cộng vào biến ans. Sau đó, in ra ans.

Trường hợp ngoại lệ: Nếu có một thành viên thuộc cả hai nhóm thì in ra -1.

Mong các anh giúp em phần này với ạ. Em kẹt gần 1 tiếng rồi…