QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398831#8593. CoinTalaodi3 3ms18188kbC++235.5kb2024-04-25 18:52:182024-04-25 18:52:23

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 18:52:23]
  • 评测
  • 测评结果:3
  • 用时:3ms
  • 内存:18188kb
  • [2024-04-25 18:52:18]
  • 提交

answer

#include <bits/stdc++.h>

namespace IO {
	template <class Stream>
	void write_int128(Stream& out, __int128 v) {
		if (v >= 10) {
			write_int128(out, v / 10);
		}
		out << (int) (v % 10);
	}

	template <class Stream>
	Stream& fmtbase(Stream& out, const char* format) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				throw std::invalid_argument("Error Number of Parameters!");
			}
			
			out << *format;
		}
		
		return out;
	}
	
	template <class Stream, class... Nxt>
	Stream& fmtbase(Stream& out, const char* format, const __int128& value, const Nxt&... nxt) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				write_int128(out, value);
				return fmtbase(out, format + 2, nxt...);
			} 
			
			out << *format;
		}
		
		throw std::invalid_argument("Error Number of Parameters!");
	}

	template <class Stream, class Fst, class... Nxt>
	Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				out << value;
				return fmtbase(out, format + 2, nxt...);
			} 
			
			out << *format;
		}
		
		throw std::invalid_argument("Error Number of Parameters!");
	}
	
	template <class... Ps>
	std::string to_string(const char* format, const Ps&... ps) {
		std::stringstream ss;
		fmtbase(ss, format, ps...);
		return ss.str();
	}

	template <class... Ps>
	std::ostream& fmtout(const char* format, const Ps&... ps) {
		return fmtbase(std::cout, format, ps...);
	}
	
	template <class... Ps>
	std::ostream& fmterr(const char* format, const Ps&... ps) {
		return fmtbase(std::cerr, format, ps...);
	}
	
	std::istream& allin() {
		return std::cin;
	}
	
	template <class Fst, class ... Nxt>
	std::istream& allin(Fst& fst, Nxt&... nxt) {
		std::cin >> fst;
		return allin(nxt...);
	}
	
	template <class Iter>
	std::istream& rangin(Iter begin, Iter end) {
		while (begin != end) {
			std::cin >> *begin;
			begin++;
		}
		
		return std::cin;
	}
	
	namespace Fast {
		bool sync = false;
		
		char buf[1 << 23];
		char *p1 = buf, *p2 = buf;
		
		void sync_with_ios(bool s) {
			sync = s;
		}
		
		inline char getchar() {
			if (sync) {
				return (char) std::cin.get();
			}
			else {
				return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin)), p1 == p2 ? EOF : *p1++;
			}
		}
		
		void read() { }
		
		template <class T, class... U>
		void read(T& x, U&... us) {
			x = 0;
			T pos = 1;
			
			char c = getchar();
			while (!isdigit(c)) {
				if (c == '-') {
					pos = -1;
				}
				
				c = getchar();
			}
			
			while (isdigit(c)) {
				x = 10 * x + c - '0';
				c = getchar();
			}
			
			x *= pos;
			read(us...);
		}
		
		template <class T>
		void write(const T& t) {
			if (t > 10) {
				write(t / 10);
			}
			
			std::cout << (int) (t % 10);
		}
	}
}

namespace Solve {
	using namespace IO;

	using ll = long long;
	using ul = unsigned long long;
	using db = double;
	using ld = long double;
	using ui = unsigned;
	using ib = __int128;
	using ub = __uint128_t;

	int const INF = std::numeric_limits<int>::max();
	int const NINF = std::numeric_limits<int>::min();
	ll const LINF = std::numeric_limits<ll>::max();
	ll const LNINF = std::numeric_limits<ll>::min();
	ld const EPS = 1e-8;

	std::mt19937_64 mt;

	ll rnd(ll l, ll r) {
		return std::uniform_int_distribution<ll>(l, r)(mt);
	}

	template <class T>
	inline int isz(const T& v) {
		return v.size();
	}

	template <class T>
	inline T& ckmx(T& a, T b) {
		return a < b ? (a = b) : a;
	}

	template <class T>
	inline T& ckmi(T& a, T b) {
		return b < a ? (a = b) : a;
	}

	int const N = 2e5 + 10;
	int const M = 8e5 + 10;

	int n, m;
	std::set<int> gr[N + 1];
	int ans[N + 1];
	int ind[N + 1];
	std::vector<std::vector<int>> cut;
	int w[N + 1];
	int p1[N + 1];
	int p2[N + 1];

	void solve(int p[N + 1]) {
		for (int i = 1; i <= n; i++) {
			for (auto& to : gr[i]) {
				ind[to]++;
			}
		}

		auto cmp = [&](int i, int j) {
			return w[i] < w[j];
		};

		int tot = 0;
		std::priority_queue<int, std::vector<int>, decltype(cmp)> hp(cmp);
		for (int i = 1; i <= n; i++) {
			if (!ind[i]) {
				hp.push(i);
			}
		}

		while (isz(hp)) {
			auto t = hp.top();
			hp.pop();

			tot++;
			p[t] = tot;
			for (auto& to : gr[t]) {
				ind[to]--;
				if (!ind[to]) {
					hp.push(to);
				}
			}
		}
	}

	void main() {
		std::cin >> n >> m;
		for (int i = 1; i <= m; i++) {
			int u, v;
			std::cin >> u >> v;
			gr[u].insert(v);
		}

		for (int i = 1; i <= n; i++) {
			w[i] = i;
		}
		solve(p1);
		std::reverse(w + 1, w + n + 1);
		solve(p2);

		for (int i = 1; i <= n; i++) {
			fmtout("{} ", p1[i] == p2[i] ? 1 : -1);
		}
	}

	void init() {
		
	}

	void clear() {

	}
}

signed main() {
#ifndef ONLINE_JUDGE
	auto input_file = freopen("d.in", "r", stdin);
	auto output_file = freopen("d.out", "w", stdout);
#endif

	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();

	IO::fmterr("seed: {}\n", seed);
	Solve::mt.seed(seed);

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int t = 1;
	// std::cin >> t;

	Solve::init();

	for (int id = 1; id <= t; id++) {
		Solve::main();
		Solve::clear();
	}

#ifndef ONLINE_JUDGE
	std::cout.flush();
	fclose(input_file);
	fclose(output_file);
#endif

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Acceptable Answer

Test #1:

score: 3
Acceptable Answer
time: 0ms
memory: 17916kb

input:

4 4
2 4
3 1
4 1
2 3

output:

1 1 -1 -1 

result:

points 0.50 -1 correct

Test #2:

score: 3
Acceptable Answer
time: 0ms
memory: 15912kb

input:

6 8
1 5
5 4
6 2
2 5
4 3
6 1
6 5
2 1

output:

1 1 1 1 1 1 

result:

points 0.50 -1 correct

Test #3:

score: 6
Accepted
time: 0ms
memory: 17988kb

input:

2 1
1 2

output:

1 1 

result:

ok ac

Test #4:

score: 3
Acceptable Answer
time: 0ms
memory: 17988kb

input:

6 12
1 5
5 4
6 2
2 5
4 3
6 5
1 5
1 5
2 4
6 3
1 3
4 3

output:

-1 -1 1 1 1 -1 

result:

points 0.50 -1 correct

Test #5:

score: 3
Acceptable Answer
time: 3ms
memory: 15860kb

input:

7 20
1 6
6 3
1 4
1 5
1 7
1 2
1 5
2 3
4 5
7 2
2 4
5 3
6 3
1 3
4 3
7 5
2 6
4 6
7 2
7 5

output:

1 1 1 1 -1 -1 1 

result:

points 0.50 -1 correct

Test #6:

score: 3
Acceptable Answer
time: 3ms
memory: 18148kb

input:

7 20
5 6
1 3
3 6
4 1
7 4
2 5
4 3
2 6
7 5
4 6
2 6
2 1
4 5
1 3
1 5
7 1
7 6
4 1
7 6
3 6

output:

1 -1 -1 -1 -1 1 -1 

result:

points 0.50 -1 correct

Test #7:

score: 3
Acceptable Answer
time: 0ms
memory: 18188kb

input:

7 20
7 6
4 5
6 4
3 6
4 1
6 2
3 5
5 2
7 6
1 2
3 6
6 4
7 1
6 1
7 1
4 5
3 6
3 5
4 5
3 1

output:

-1 1 -1 1 -1 1 -1 

result:

points 0.50 -1 correct

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

50%
Acceptable Answer

Test #8:

score: 0
Wrong Answer
time: 2ms
memory: 16068kb

input:

20 100
5 20
4 5
18 16
1 13
14 9
11 19
6 4
7 20
16 11
8 13
4 5
16 9
12 14
7 12
11 3
9 11
9 11
13 6
3 10
12 9
13 4
20 12
13 6
18 11
5 7
5 7
15 18
12 15
17 13
15 18
3 2
11 2
11 2
15 19
4 19
14 19
14 9
17 3
1 18
8 10
16 19
1 6
7 2
5 12
1 18
8 20
5 18
8 5
4 16
1 15
5 19
18 19
17 10
1 10
17 3
10 2
3 10
17...

output:

-1 -1 -1 1 1 1 1 1 1 -1 1 1 1 -1 1 -1 -1 -1 -1 1 

result:

wrong answer wa

Subtask #3:

score: 0
Skipped

Dependency #1:

50%
Acceptable Answer

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

50%
Acceptable Answer

Dependency #2:

0%