QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#432027#2017. 排水系统Nevll80 70ms12224kbC++141.5kb2024-06-06 16:35:352024-06-06 16:35:36

Judging History

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

  • [2024-06-06 16:35:36]
  • 评测
  • 测评结果:80
  • 用时:70ms
  • 内存:12224kb
  • [2024-06-06 16:35:35]
  • 提交

answer

# include <bits/stdc++.h>
# define ll __int128_t
# define fi first
# define se second
# define pii pair<int, int>
using namespace std;

vector<int> edge[100001];
int in[100001];
pair<ll, ll> val[100001];

void ad(pair<ll, ll> &a, pair<ll, ll> b) {
	ll c = a.fi * b.se + a.se * b.fi;
	ll d = a.se * b.se;
	
	if(c == 0) {
		a = {0, 1};
		return;
	}
	
	ll e = __gcd(c, d);
	c /= e;
	d /= e;
	a = {c, d};
	return;
}

void prnt(ll a) {
	vector<int> ck;
	ck.clear();
	while(a > 0) {
		ck.push_back(a%10);
		a /= ((ll) 10);
	}
	for(int i=ck.size()-1;i>=0;i--) printf("%d", ck[i]);
}

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	for(int i=1;i<=N;i++) {
		val[i] = {0, 1};
		int K;
		scanf("%d", &K);
		while(K--) {
			int x;
			scanf("%d", &x);
			edge[i].push_back(x);
			in[x]++;
		}
	}
	
	val[M] = {1, 1};
	
	vector<int> nw;
	nw.clear();
	
	for(int i=1;i<=N;i++) {
		if(!in[i]) {
			nw.push_back(i);
		}
	}
	
	while(nw.size()) {
		int v = nw.back();
		nw.pop_back();
		
		if(edge[v].size() == 0) continue;
		
		if(val[v].fi != 0) {
			ll e = __gcd(val[v].fi, (ll) edge[v].size());
			val[v].fi /= e;
			val[v].se = (edge[v].size()) / e * val[v].se;
		} else val[v].se = 1ll;
		
		for(auto p : edge[v]) {
			in[p]--;
			ad(val[p], val[v]);
			if(!in[p]) nw.push_back(p);
		}
	}
	
	for(int i=1;i<=N;i++) {
		if(edge[i].size() == 0) {
			prnt(val[i].fi);
			printf(" ");
			prnt(val[i].se);
			printf("\n");
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 2ms
memory: 8436kb

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

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

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

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

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: 2ms
memory: 7396kb

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: 55ms
memory: 11992kb

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: 70ms
memory: 12008kb

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: 0
Wrong Answer
time: 47ms
memory: 12224kb

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
 1
 1
1 1250000
 1
 1
 1
1 1953125
1 5625
13 1562500
1 1875000
 1
 1
 1
231 15625000
1 1875000
1 1953125
 1
157 11718750
79 3750000
 1
1 23437500
253 2343750
 1
1 18750000
1 781250
1 1953125
 1
 1
109 7031250
 1
1 1875000
1 140625
43 1562500
1 1875000
1259 225000000
 1
13 600000
1 18750000
 1
19 ...

result:

wrong answer 2nd words differ - expected: '48828125', found: '1'

Test #10:

score: 0
Wrong Answer
time: 42ms
memory: 11960kb

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
 1
 1
1 468750
 1
 1
 1
 1
 1
 1
 1
 1
 1
1 31250
 1
 1
41 15000000
 1
 1
 1
1 5859375
 1
 1
 1
 1
 1
 1
 1
1 187500
 1
 1
 1
 1
 1
 1
1 60000
 1
1 9375000
 1
1 150000
1 56250
 1
1 112500
1 703125
 1
1 1500000
 1
1 56250
 1
 1
 1
1 703125
 1
1 33750
1 225000
 1
 1
1 1687500
1 50000
 1
 1
1 937500...

result:

wrong answer 2nd words differ - expected: '48828125', found: '1'