QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782640 | #2017. 排水系统 | Link_Cut_Y# | 100 ✓ | 52ms | 52148kb | C++20 | 3.7kb | 2024-11-25 20:49:14 | 2024-11-25 20:49:14 |
Judging History
answer
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define int __int128
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )
#define Darr(a, L, R) (cerr << #a "[" << L << " ~ " << R << "] = "; rep(x, L, R) cerr << a[x] << " "; cerr << '\n';)
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define D(x) (cerr << #x << " = " << x << '\n')
#define vit vector<int>::iterator
#define all(x) x.begin(), x.end()
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define chkmin(a, b) (a = min(a, b))
#define chkmax(a, b) (a = max(a, b))
#define sit set<int>::iterator
#define lowbit(x) (x & -x)
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pi acos(-1)
#define gc getchar
#define pc putchar
#define db double
#define y second
#define x first
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int mod = 998244353;
const int eps = 1e-9;
const int N = 1000010; int T = 1;
void print(int x) { dep(i, 20, 0) pc(((x >> i) & 1) ? '1' : '0'); }
int qpow(int a, int b = mod - 2, int s = 1) { for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) s = 1ll * s * a % mod; return s; }
namespace IO {
void read() { return; }
void write(char ch) { pc(ch); return; }
void write() { return; }
template <typename T> void read(T &x) { x = 0; T w = 0; char ch = gc(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = gc(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc(); x = w ? -x : x; }
template <typename T> void print(T x) { if (!x) return; print<T>(x / 10), pc((x % 10) ^ '0'); }
template <typename T> void write(T x) { if (x > 0) print<T>(x); else if (x < 0) pc('-'), print<T>(-x); else pc('0'); }
template <typename T> void write(T x, char en) { write<T>(x), pc(en); }
template <typename T, typename ...T2> void read(T &s, T2 &...oth) { read(s); read(oth...); return; }
}; using namespace IO;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
struct Frac {
int s, t;
void R() {
if (t == 0) s = 0;
else if (s == 0) t = 1;
else { int d = gcd(s, t); s /= d, t /= d; }
}
Frac() { s = 0, t = 1; }
Frac(int a, int b) { s = a, t = b; R(); }
Frac operator + (const Frac &p)const { return Frac(s * p.t + p.s * t, t * p.t); }
Frac operator - (const Frac &p)const { return Frac(s * p.t - p.s * t, t * p.t); }
Frac operator * (const Frac &p)const { return Frac(s * p.s, t * p.t); }
Frac operator / (const Frac &p)const { return Frac(s * p.t, t * p.s); }
Frac operator * (const int &p)const { return Frac(s * p, t); }
Frac operator / (const int &p)const { return Frac(s, t * p); }
}f[N];
int n, m, d[N], dt[N];
vector<int> E[N];
void sub() {
read(n, m);
vector<int> outer;
rep(i, 1, n) {
int t; read(t);
if (!t) outer.pb(i);
while (t -- ) {
int v; read(v);
E[i].pb(v); d[v] ++ ;
}
} rep(i, 1, n) dt[i] = d[i];
queue<int> q;
rep(i, 1, n) if (!d[i]) q.push(i), f[i] = Frac(1, 1);
while (q.size()) {
auto t = q.front(); q.pop();
for (auto v : E[t]) {
f[v] = f[v] + f[t] / (int)E[t].size();
d[v] -- ; if (!d[v]) q.push(v);
}
} for (auto i : outer)
write(f[i].s, ' '), write(f[i].t, '\n');
}
signed main() {
// read(T);
while (T -- ) sub();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 39448kb
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: 39976kb
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: 3ms
memory: 37996kb
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: 10
Accepted
time: 3ms
memory: 38780kb
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:
ok 636 tokens
Test #5:
score: 10
Accepted
time: 0ms
memory: 40020kb
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:
ok 626 tokens
Test #6:
score: 10
Accepted
time: 0ms
memory: 40952kb
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:
ok 652 tokens
Test #7:
score: 10
Accepted
time: 37ms
memory: 51928kb
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:
ok 93056 tokens
Test #8:
score: 10
Accepted
time: 36ms
memory: 51480kb
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:
ok 84746 tokens
Test #9:
score: 10
Accepted
time: 47ms
memory: 49588kb
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 2538341 10546875000 15673 2343750000 759673 2343750000 54145169317349 3023308800000000000 1 59049 1 1048576 2003363 600000000000 790936213 3686400000000 7805087 150000000000 233 390625000 68035921 737280000000 173243 37500000000 938137 585937500 122493287 759375000000 6499 1171875000 8570...
result:
ok 64816 tokens
Test #10:
score: 10
Accepted
time: 52ms
memory: 52148kb
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 191216299 675000000000 3778533703 48600000000000 214192764230063 36279705600000000000 1 59049 74674 2767921875 8222897 553584375000 1 1048576 720274069 2949120000000 1058701 42467328000 130372058357 663552000000000 45101357 409600000000 3563743 14062500000 946441 81920000000 27...
result:
ok 64158 tokens
Extra Test:
score: 0
Extra Test Passed