Submission #863945

#	Time	Username	Problem	Language	Result	Execution time	Memory
863945		aaron_dcoder	Povjerenstvo (COI22_povjerenstvo)	C++17	0 / 100	278 ms	93584 KiB

Main

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e11;

vector<vector<ll>> hate;
vector<vector<ll>> hatedby;

vector<ll> sign;

void dfs(ll node) {
	dbgv(node << " " << sign[node]);
	for (ll hater : hatedby[node])
	{
		if (sign[hater] == 0) {
			sign[hater] = -sign[node];
			dbgv(hater << " " << sign[hater]);
			dfs(hater);
		}
	}

	for (ll fku : hate[node])
	{
		if (sign[fku] == 0) {
			sign[fku] = -sign[node];
			dbgv(fku << " " << sign[fku]);
			dfs(fku);
		}
	}

}

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

	ll N,M;
	cin >> N >> M;

	hatedby.assign(N,{});
	hate.assign(N,{});
	sign.assign(N,0);

	for (int i = 0; i < M; ++i)
	{
		ll a,b;
		cin >> a >> b;
		a--;
		b--;
		hate[a].push_back(b);
		hatedby[b].push_back(a);
	}
	dbgfor (int i :hatedby[0]) 
	{
		dbgv(i);
	}
dbg("chkpnt 1");

	for (ll i = 0; i < N; ++i)
	{
		if (sign[i]==0) {
			sign[i] = 10+i;
			dfs(i);
		}
	}

	set<ll> invalidsigns;
	for (ll i = 0; i < N; ++i)
	{
		if (hate[i].empty()) {
			invalidsigns.insert(-sign[i]);
			if (invalidsigns.count(sign[i])>0) {
				cout << "-1";
				return 0;
			}
		}
	}

	dbgfor (int i : invalidsigns)
	{
		dbgv(i);
	}

	vector<ll> comm;

	for (ll i = 0; i < N; ++i)
	{
		if (sign[i]<0) {
			if (invalidsigns.count(-sign[i])>0) {
				comm.push_back(i);
			}
		}
		else if (sign[i]>0) {
			if (invalidsigns.count(sign[i])==0) {
				comm.push_back(i);
			}
		}
		else throw exception();
	}

	cout << comm.size() << "\n";
	for (ll p : comm)
	{
		cout << p+1 << " ";
	}

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:14: warning: unused variable 'i' [-Wunused-variable]
   73 |  dbgfor (int i :hatedby[0])
      |              ^
Main.cpp:6:48: note: in definition of macro 'dbgfor'
    6 | #define dbgfor(COND) if constexpr (false) for (COND)
      |                                                ^~~~
Main.cpp:99:14: warning: unused variable 'i' [-Wunused-variable]
   99 |  dbgfor (int i : invalidsigns)
      |              ^
Main.cpp:6:48: note: in definition of macro 'dbgfor'
    6 | #define dbgfor(COND) if constexpr (false) for (COND)
      |                                                ^~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33