QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398671 | #8593. Coin | Talaodi | 0 | 4ms | 14340kb | C++23 | 5.5kb | 2024-04-25 16:23:32 | 2024-04-25 16:23:32 |
Judging History
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;
void main() {
std::cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
std::cin >> u >> v;
gr[u].insert(v);
ind[v]++;
}
std::vector<int> vs;
for (int i = 1; i <= n; i++) {
if (!ind[i]) {
vs.push_back(i);
}
}
while (isz(vs)) {
cut.push_back(vs);
std::vector<int> nvs;
for (auto& v : vs) {
for (auto& to : gr[v]) {
ind[to]--;
if (!ind[to]) {
nvs.push_back(to);
}
}
}
vs = nvs;
}
for (int i = 0; i < isz(cut); i++) {
if (isz(cut[i]) > 1) {
continue;
}
int x = cut[i][0];
int is = 1;
if (i > 0) {
for (auto& v : cut[i - 1]) {
if (!gr[v].count(x)) {
is = 0;
}
}
}
if (i + 1 < isz(cut)) {
for (auto& v : cut[i + 1]) {
if (!gr[x].count(v)) {
is = 0;
}
}
}
ans[x] = is;
}
for (int i = 1; i <= n; i++) {
fmtout("{} ", ans[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: 0
Wrong Answer
Test #1:
score: 3
Acceptable Answer
time: 4ms
memory: 12948kb
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: 13076kb
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: 13340kb
input:
2 1 1 2
output:
1 1
result:
ok ac
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 14340kb
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:
wrong answer wa
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%