oj.uz

Submission #863945

# Submission time Handle Problem Language Result Execution time Memory
863945 2023-10-21T14:06:58 Z aaron_dcoder Povjerenstvo (COI22_povjerenstvo) C++17
0 / 100
 278 ms 93584 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 93160 KB Output is correct
2 Correct 132 ms 65988 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 169 ms 56124 KB Output is correct
5 Correct 165 ms 60624 KB Output is correct
6 Correct 134 ms 52900 KB Output is correct
7 Correct 97 ms 49336 KB Output is correct
8 Correct 119 ms 52296 KB Output is correct
9 Correct 278 ms 59332 KB Output is correct
10 Incorrect 198 ms 50744 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 93584 KB Output is correct
2 Correct 115 ms 53952 KB Output is correct
3 Correct 84 ms 46864 KB Output is correct
4 Incorrect 248 ms 51072 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Incorrect 2 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 93160 KB Output is correct
2 Correct 132 ms 65988 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 169 ms 56124 KB Output is correct
5 Correct 165 ms 60624 KB Output is correct
6 Correct 134 ms 52900 KB Output is correct
7 Correct 97 ms 49336 KB Output is correct
8 Correct 119 ms 52296 KB Output is correct
9 Correct 278 ms 59332 KB Output is correct
10 Incorrect 198 ms 50744 KB Output isn't correct
11 Halted 0 ms 0 KB -