QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #302953 | #2017. 排水系统 | Wood | 30 | 62ms | 11488kb | C++23 | 3.3kb | 2024-01-11 16:01:16 | 2024-01-11 16:01:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
using i128 = __int128;
istream &operator>>(istream &is, i128 &n) {
n = 0;
string s;
is >> s;
for (auto c : s) {
n = 10 * n + c - '0';
}
return is;
}
ostream &operator<<(ostream &os, i128 n) {
if (n == 0) {
return os << 0;
}
string s;
while (n > 0) {
s += '0' + n % 10;
n /= 10;
}
reverse(s.begin(), s.end());
return os << s;
}
i128 gcd(i128 a, i128 b) {
return b ? gcd(b, a % b) : a;
}
struct Frac {
i128 num;
i128 den;
Frac(i128 num_, i128 den_) : num(num_), den(den_) {
if (den < 0) {
den = -den;
num = -num;
}
}
Frac() : Frac(0, 1) {}
Frac(i128 num_) : Frac(num_, 1) {}
explicit operator double() const {
return 1. * num / den;
}
Frac &operator+=(Frac rhs) {
num = num * rhs.den + rhs.num * den;
den *= rhs.den;
return *this;
}
Frac &operator-=(Frac rhs) {
num = num * rhs.den - rhs.num * den;
den *= rhs.den;
return *this;
}
Frac &operator*=(const Frac &rhs) {
num *= rhs.num;
den *= rhs.den;
return *this;
}
Frac &operator/=(const Frac &rhs) {
num *= rhs.den;
den *= rhs.num;
if (den < 0) {
num = -num;
den = -den;
}
return *this;
}
friend Frac operator+(Frac lhs, const Frac &rhs) {
return lhs += rhs;
}
friend Frac operator-(Frac lhs, const Frac &rhs) {
return lhs -= rhs;
}
friend Frac operator*(Frac lhs, const Frac &rhs) {
return lhs *= rhs;
}
friend Frac operator/(Frac lhs, const Frac &rhs) {
return lhs /= rhs;
}
friend Frac operator-(Frac &a) {
return Frac(-a.num, a.den);
}
friend bool operator==(Frac lhs, Frac rhs) {
return lhs.num * rhs.den == rhs.num * lhs.den;
}
friend bool operator!=(Frac lhs, Frac rhs) {
return lhs.num * rhs.den != rhs.num * lhs.den;
}
friend bool operator<(Frac lhs, Frac rhs) {
return lhs.num * rhs.den < rhs.num * lhs.den;
}
friend bool operator>(Frac lhs, Frac rhs) {
return lhs.num * rhs.den > rhs.num * lhs.den;
}
friend bool operator<=(Frac lhs, Frac rhs) {
return lhs.num * rhs.den <= rhs.num * lhs.den;
}
friend bool operator>=(const Frac &lhs, const Frac &rhs) {
return lhs.num * rhs.den >= rhs.num * lhs.den;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
vector<int> deg(n);
for (int i = 0; i < n; i++) {
int d;
cin >> d;
while (d--) {
int a;
cin >> a;
a--;
deg[a]++;
adj[i].push_back(a);
}
}
vector<Frac> a(n);
queue<int> q;
for (int i = 0; i < n; i++) {
if (!deg[i]) {
a[i] = Frac(1, 1);
q.push(i);
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
if (!adj[x].empty()) {
Frac v = a[x] / Frac((i128) adj[x].size(), 1);
for (auto y : adj[x]) {
a[y] += v;
if (!--deg[y]) {
q.push(y);
}
}
}
}
for (int i = 0; i < n; i++) {
if (adj[i].empty()) {
i128 x = a[i].num;
i128 y = a[i].den;
i128 g = gcd(x, y);
x /= g, y /= g;
cout << x << ' ' << y << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 3548kb
input:
10 1 4 2 3 4 5 3 6 7 8 3 7 10 8 1 7 2 8 10 2 8 9 2 9 8 1 10 1 10 0
output:
1 1
result:
ok 2 tokens
Test #2:
score: 10
Accepted
time: 0ms
memory: 3444kb
input:
10 1 5 2 3 4 5 7 3 6 7 9 3 7 8 9 3 8 9 6 1 7 2 9 10 2 10 9 0 0 0
output:
2 15 8 15 1 3
result:
ok 6 tokens
Test #3:
score: 10
Accepted
time: 0ms
memory: 3436kb
input:
10 1 5 2 3 4 5 8 4 6 8 7 9 2 7 6 4 8 6 9 10 2 9 8 1 10 0 0 1 10 0
output:
3 20 2 5 9 20
result:
ok 6 tokens
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 3652kb
input:
1000 1 5 2 3 4 5 468 5 6 7 8 9 72 5 10 11 12 13 658 5 14 15 16 17 100 5 18 19 20 21 129 5 22 23 24 25 146 5 26 27 28 29 91 5 30 31 32 33 337 5 34 35 36 37 694 5 38 39 40 41 766 5 42 43 44 45 986 5 46 47 48 49 365 5 50 51 52 53 176 5 54 55 56 57 489 5 58 59 60 61 469 5 62 63 64 65 984 5 66 67 68 69 2...
output:
1 625 1 625 1 625 1 625 1 625 1 625 1 625 1 3125 1 3125 2 3125 3 3125 2 3125 47 37500 1 2500 1 2500 2 3125 39 6250 2 3125 1 3125 626 3125 83 9375 26 3125 31 3125 2 3125 1 3125 9 6250 3 3125 9 12500 37 18750 1 3125 1 3125 2 3125 9 12500 1 3125 17 6250 33 3125 2 3125 3 3125 1 2500 9 12500 1 3125 13 12...
result:
wrong answer 469th words differ - expected: '57', found: '23341237068515110361731859498179697036'
Test #5:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
1000 1 5 2 3 4 5 257 5 6 7 8 9 948 5 10 11 12 13 633 5 14 15 16 17 1000 5 18 19 20 21 105 5 22 23 24 25 662 5 26 27 28 29 648 5 30 31 32 33 394 5 34 35 36 37 504 5 38 39 40 41 151 5 42 43 44 45 155 5 46 47 48 49 783 4 50 51 52 53 5 54 55 56 57 249 5 58 59 60 61 432 5 62 63 64 65 423 5 66 67 68 69 70...
output:
1 625 1 625 6 625 2 625 1 625 1 625 1 625 1 625 1 625 1 625 1 500 1 1875 1 1250 1 2500 9 6250 1 2500 7 6250 8 9375 1 3125 1 375 1 2500 1 2000 1 1500 7 7500 4 1875 13 9375 2 3125 1 1500 1 1500 1 1500 1 1500 2 1875 1 1500 9 10000 1 2000 21 10000 9 2500 669 1000000 1 5000 2359 3000000 29 31250 23 15000...
result:
wrong answer 127th words differ - expected: '1571', found: '25718691176734864711761474609375'
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 3596kb
input:
1000 1 5 2 3 4 5 799 5 6 7 8 9 587 5 10 11 12 13 694 5 14 15 16 17 865 5 18 19 20 21 10 5 22 23 24 25 69 5 26 27 28 29 337 5 30 31 32 33 607 5 34 35 36 37 989 5 38 39 40 41 291 5 42 43 44 45 309 5 46 47 48 49 44 5 50 51 52 53 854 5 54 55 56 57 209 5 58 59 60 61 502 5 62 63 64 65 597 5 66 67 68 69 60...
output:
1 625 1 625 1 625 1 625 1 625 1 625 2 625 6 625 9 6250 9 2500 1 2000 9 10000 1 2500 1 2500 1 2500 2 1875 3 1250 1 500 3 3125 47 37500 8 9375 1 3125 1 3125 1 750 67 37500 1 2500 3 3125 1 1250 1 300 2 3125 41 18750 2 1875 89 37500 11 9375 16 1875 8 9375 1 2500 1 2500 1 3125 29 6250 1 1000 1 1000 7 500...
result:
wrong answer 209th words differ - expected: '53', found: '8819641163480732601460776180839169'
Test #7:
score: 0
Wrong Answer
time: 39ms
memory: 11424kb
input:
100000 1 5 2 3 4 5 7783 5 6 7 8 9 21991 5 10 11 12 13 45651 5 14 15 16 17 56745 5 18 19 20 21 84002 5 22 23 24 25 94984 5 26 27 28 29 16303 5 30 31 32 33 30894 5 34 35 36 37 37939 5 38 39 40 41 61574 5 42 43 44 45 72828 5 46 47 48 49 92611 5 50 51 52 53 11795 5 54 55 56 57 22587 5 58 59 60 61 36800 ...
output:
1 15625 1 15625 1 15625 1 15625 1 15625 1 78125 1 62500 1 78125 1 78125 1 78125 1 78125 1 78125 2 78125 1 78125 7 234375 6 390625 1 390625 1 390625 1 390625 1 390625 2 390625 2 390625 2 390625 1 312500 1 390625 1 156250 7 781250 1 390625 1 390625 7 390625 2 390625 1 390625 1 390625 6 390625 33 39062...
result:
wrong answer 2837th words differ - expected: '51', found: '483169060316868126392364501953125'
Test #8:
score: 0
Wrong Answer
time: 62ms
memory: 11160kb
input:
100000 1 5 2 3 4 5 6025 5 6 7 8 9 32221 5 10 11 12 13 39240 5 14 15 16 17 55392 5 18 19 20 21 69386 5 22 23 24 25 97544 5 26 27 28 29 16414 5 30 31 32 33 32966 5 34 35 36 37 41376 5 38 39 40 41 66116 5 42 43 44 45 83340 5 46 47 48 49 90236 5 50 51 52 53 13716 5 54 55 56 57 32168 5 58 59 60 61 43106 ...
output:
1 12500 1 15625 1 15625 1 15625 1 15625 1 12500 1 15625 1 12500 1 12500 1 15625 1 15625 1 15625 1 12500 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 15625 1 12500 1 8000 1 15625 1 15625 1 15625 1 15625 1 156...
result:
wrong answer 3599th words differ - expected: '201', found: '380850906367413699626922607421875'
Test #9:
score: 0
Wrong Answer
time: 56ms
memory: 11488kb
input:
100000 10 5 11 12 13 14 15 3 66 67 68 4 96 97 98 99 5 1274 1643 2223 2242 2626 5 5407 8119 10748 19818 29900 5 178 180 316 323 1080 5 274 596 716 1923 2001 5 1497 8384 9739 16776 18532 5 165 211 240 289 985 5 170 179 197 222 1011 5 16 17 18 19 20 5 164 322 540 590 1641 5 340 4731 14181 50729 55910 5...
output:
1 48828125 224396667545079253613948822021484375 15673 2343750000 693337147638534800550150995291924805 583856452886532714555483468557047984 54145169317349 3023308800000000000 1 59049 1 1048576 2003363 600000000000 1421323590132692083688282704246115539 982220648627584960217998782542905344 6613534991...
result:
wrong answer 3rd words differ - expected: '2538341', found: '224396667545079253613948822021484375'
Test #10:
score: 0
Runtime Error
input:
100000 10 5 11 12 13 14 15 3 66 67 68 4 98 99 100 101 5 193 213 239 613 1656 5 187 259 453 513 3129 5 148 606 2076 5693 30126 5 748 1455 3800 4919 8049 5 264 419 516 868 1222 5 260 19073 24446 65904 50227 5 196 4456 4784 83171 95673 5 16 17 18 19 20 5 182 277 388 1070 2021 5 279 1317 4410 14701 2557...
output:
1 48828125 1 48828125 218569990359630192577461745152 153704588652364433272832 214192764230063 36279705600000000000 1 59049 74674 2767921875 8222897 553584375000 1 1048576 243291296923453837391899398305 1058701 42467328000 7509163154607979299176493 18232152753961226179969024 45101357 409600000000 ...