QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398693#8593. CoinTalaodi16 4ms4032kbC++235.1kb2024-04-25 16:32:442024-04-25 16:32:44

Judging History

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

  • [2024-04-25 16:32:44]
  • 评测
  • 测评结果:16
  • 用时:4ms
  • 内存:4032kb
  • [2024-04-25 16:32:44]
  • 提交

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 = 1010;

	int n, m;
	std::set<int> gr[N + 1];
	int ans[N + 1];
	std::bitset<N + 1> rch[N + 1];
	int vis[N + 1];

	void dfs(int x) {
		vis[x] = 1;
		rch[x][x] = 1;
		for (auto& to : gr[x]) {
			if (!vis[to]) {
				dfs(to);
			}
			rch[x] |= rch[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++) {
			if (!vis[i]) {
				dfs(i);
			}
		}

		for (int i = 1; i <= n; i++) {
			int is = 1;
			for (int j = 1; j <= n; j++) {
				if (!rch[i][j] && !rch[j][i]) {
					is = 0;
				}
			}
			fmtout("{} ", is ? 1 : -1);
		}
		fmtout("\n");
	}

	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;
}

詳細信息

Subtask #1:

score: 3
Acceptable Answer

Test #1:

score: 3
Acceptable Answer
time: 1ms
memory: 3688kb

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: 3620kb

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: 3684kb

input:

2 1
1 2

output:

1 1 

result:

ok ac

Test #4:

score: 3
Acceptable Answer
time: 1ms
memory: 3856kb

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: 1ms
memory: 3916kb

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: 0ms
memory: 3744kb

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: 3748kb

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: 8
Acceptable Answer

Dependency #1:

50%
Acceptable Answer

Test #8:

score: 8
Acceptable Answer
time: 0ms
memory: 3752kb

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:

points 0.50 -1 correct

Test #9:

score: 8
Acceptable Answer
time: 1ms
memory: 3660kb

input:

100 400
87 45
42 17
9 81
65 10
8 82
76 48
39 73
21 58
76 30
76 92
74 76
99 90
38 50
86 74
75 52
8 2
80 55
20 95
66 60
78 82
10 18
22 59
23 17
63 76
56 51
38 10
50 65
41 28
64 77
59 53
100 66
38 84
23 47
17 9
45 75
41 28
33 41
8 78
2 95
3 11
40 15
60 63
23 17
82 2
61 44
44 16
77 34
100 66
96 99
68 12...

output:

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

result:

points 0.50 -1 correct

Subtask #3:

score: 5
Acceptable Answer

Dependency #1:

50%
Acceptable Answer

Dependency #2:

50%
Acceptable Answer

Test #10:

score: 5
Acceptable Answer
time: 4ms
memory: 4032kb

input:

1000 4000
619 298
211 477
584 418
812 280
978 268
280 345
715 364
73 664
915 819
535 28
110 959
384 663
773 315
792 250
374 80
134 202
779 416
613 334
318 756
21 812
424 997
664 277
151 963
299 438
955 988
532 653
521 43
121 20
902 849
237 305
272 893
325 792
469 549
891 531
612 810
294 256
188 990
...

output:

-1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1...

result:

points 0.50 -1 correct

Test #11:

score: 5
Acceptable Answer
time: 3ms
memory: 3924kb

input:

1000 4000
229 403
665 867
715 618
306 900
423 567
515 288
39 754
782 321
516 969
432 89
304 726
837 39
648 991
870 369
84 681
864 41
682 940
565 914
724 763
694 112
969 815
864 41
975 868
662 803
707 465
905 791
116 115
823 578
949 588
589 522
775 447
795 130
366 456
993 910
187 396
102 774
143 90
9...

output:

1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -...

result:

points 0.50 -1 correct

Test #12:

score: 5
Acceptable Answer
time: 1ms
memory: 3988kb

input:

1000 4000
693 317
927 745
607 353
336 456
182 240
100 824
252 317
88 828
436 714
833 621
533 704
63 735
522 518
900 283
135 829
627 459
601 176
876 806
573 140
380 898
870 795
990 876
943 148
500 462
808 486
920 463
794 7
531 181
60 105
497 875
859 469
997 575
706 838
296 194
453 793
310 673
771 307...

output:

1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 -1 1 -1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 1 1 -...

result:

points 0.50 -1 correct

Subtask #4:

score: 0
Runtime Error

Dependency #1:

50%
Acceptable Answer

Dependency #2:

50%
Acceptable Answer

Dependency #3:

50%
Acceptable Answer

Test #13:

score: 0
Runtime Error

input:

10000 24156
6770 9800
71 3709
5373 2058
9145 5993
9973 456
1562 628
839 3483
9354 9169
7105 7062
4434 4044
2147 534
7337 1981
719 3853
8205 8198
1286 7343
246 4189
1324 8878
547 3468
2219 8650
7265 5823
6382 5720
6219 1258
8893 466
5615 9147
7763 7160
3652 6512
7594 7169
235 1287
6487 2049
6894 853
...

output:


result: