QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398831 | #8593. Coin | Talaodi | 3 | 3ms | 18188kb | C++23 | 5.5kb | 2024-04-25 18:52:18 | 2024-04-25 18:52:23 |
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;
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%