QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#900820#10096. Generating Random Trees米哈游也干了 (Naihui Jiang, Kainian Zhu, Liqiang Shang)#AC ✓72ms3840kbC++231.6kb2025-02-15 17:16:232025-02-15 17:16:31

Judging History

This is the latest submission verdict.

  • [2025-02-15 17:16:31]
  • Judged
  • Verdict: AC
  • Time: 72ms
  • Memory: 3840kb
  • [2025-02-15 17:16:23]
  • Submitted

answer

#include <bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define el '\n'
#define all(x) (x).begin(), (x).end()
#define FINISH cout << "FINISH" << endl;
#define debug(x) cout << #x << " :== " << x << endl;
#define debugv(x)\
    cout << #x << " :: ";\
    for (auto v : x) cout << v << " ";\
    cout << endl;

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int mod = 998244353;
const int inf = 0x3f3f3f3f;

struct Data {
	long long p;
	int idx, rnk;
};

long long getp(int n)
{
	vector<ll> inp(n + 1, 0);

	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		inp[x]++, inp[y]++;
	}

	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += inp[i] * inp[i];
	}
	// cout << ans << el;
	return ans;
}

void solve() 
{
    int n, k;
    cin >> n >> k;
    vector<Data> v(k * 2 + 1); 
    for (int i = 1; i <= k * 2; i++) {
    	long long p = getp(n);
    	v[i].idx = i;
    	v[i].p = p;

    	// cout << p << endl;
    }
    sort(next(v.begin()), v.end(), [&] (Data x, Data y) {
    	return x.p < y.p;
    });
    for (int i = 1; i <= k * 2; i++) {
    	v[i].rnk = i;
    }
    sort(next(v.begin()), v.end(), [&] (Data x, Data y) {
    	return x.idx < y.idx;
    });
    for (int i = 1; i <= k * 2; i++) {
    	if (v[i].rnk > k) {
    		cout << "DSU" << el;
    	}
    	else {
    		cout << "Uniform" << el;
    	}
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}


这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

4 2
3 2
1 4
1 3
2 1
3 2
4 1
4 1
3 2
2 4
1 4
3 1
2 1

output:

Uniform
Uniform
DSU
DSU

result:

ok participant made 2 mistakes out of allowed 20

Test #2:

score: 0
Accepted
time: 69ms
memory: 3712kb

input:

10000 50
521 2013
4662 8507
3864 3117
382 7022
1141 1073
1493 1668
6936 8886
1739 9754
6783 9485
3305 9004
6390 1738
7386 988
8265 5088
8193 4713
3011 3132
3852 4363
3792 3497
6701 2716
4986 1884
508 3555
7147 6316
2598 3029
8799 354
963 306
802 6858
4516 6557
816 7308
535 2308
8609 1396
617 518
283...

output:

DSU
DSU
DSU
Uniform
Uniform
DSU
Uniform
Uniform
DSU
DSU
Uniform
Uniform
Uniform
DSU
Uniform
Uniform
DSU
Uniform
DSU
DSU
Uniform
DSU
DSU
Uniform
Uniform
Uniform
Uniform
DSU
DSU
DSU
Uniform
DSU
DSU
DSU
Uniform
Uniform
Uniform
Uniform
DSU
DSU
Uniform
DSU
Uniform
Uniform
Uniform
DSU
DSU
DSU
Uniform
Unif...

result:

ok participant made 0 mistakes out of allowed 20

Test #3:

score: 0
Accepted
time: 70ms
memory: 3712kb

input:

10000 50
4251 4098
5520 989
1453 8492
2057 9954
71 3614
7280 1157
991 6527
7166 7539
563 7243
7036 8324
9969 1577
8781 2031
7363 6144
397 1445
6686 7932
1046 8267
8811 7491
7430 4730
5566 4211
5249 5077
2776 3450
985 9184
6508 1655
8658 4185
8981 1738
9989 9082
308 4580
6783 663
274 3214
5731 557
69...

output:

Uniform
Uniform
Uniform
DSU
Uniform
Uniform
DSU
Uniform
Uniform
DSU
Uniform
DSU
DSU
DSU
DSU
Uniform
Uniform
Uniform
Uniform
DSU
DSU
Uniform
Uniform
DSU
DSU
DSU
Uniform
Uniform
Uniform
Uniform
Uniform
DSU
Uniform
DSU
Uniform
DSU
Uniform
DSU
Uniform
DSU
DSU
DSU
Uniform
Uniform
Uniform
DSU
Uniform
DSU
...

result:

ok participant made 0 mistakes out of allowed 20

Test #4:

score: 0
Accepted
time: 69ms
memory: 3840kb

input:

10000 50
6959 2683
6622 5891
5151 8433
8114 831
8437 9318
4134 5319
7926 1225
3575 1176
5145 5021
7202 7334
8871 6529
3776 9169
6251 7327
7701 4862
5919 3606
3276 5862
9153 5062
349 144
5586 9948
3959 4708
694 5417
2481 2273
4743 5736
2334 1951
6710 8536
1588 7169
9803 7779
2598 9051
1763 6185
6981 ...

output:

DSU
Uniform
DSU
DSU
DSU
DSU
Uniform
DSU
DSU
Uniform
DSU
DSU
DSU
Uniform
Uniform
Uniform
Uniform
Uniform
DSU
DSU
DSU
Uniform
Uniform
DSU
Uniform
DSU
Uniform
Uniform
Uniform
Uniform
DSU
DSU
Uniform
DSU
DSU
DSU
Uniform
Uniform
DSU
DSU
DSU
Uniform
Uniform
Uniform
DSU
DSU
DSU
Uniform
DSU
DSU
Uniform
Unif...

result:

ok participant made 0 mistakes out of allowed 20

Test #5:

score: 0
Accepted
time: 68ms
memory: 3840kb

input:

10000 50
8881 9191
203 4418
7574 6636
210 7041
1492 8011
5995 6535
3093 1578
6942 4972
2308 8222
4512 9261
8592 9802
7838 1367
26 6916
6485 6044
3211 8362
9418 3462
5512 4358
8831 4572
9842 3333
4146 5963
1600 3935
8067 4027
1333 4966
8848 8435
2770 7032
2610 831
9882 7876
6371 648
9064 2473
5818 70...

output:

DSU
Uniform
Uniform
DSU
Uniform
DSU
DSU
DSU
Uniform
DSU
DSU
DSU
DSU
Uniform
DSU
DSU
Uniform
DSU
Uniform
Uniform
DSU
DSU
Uniform
Uniform
DSU
DSU
DSU
Uniform
Uniform
Uniform
Uniform
DSU
DSU
DSU
Uniform
DSU
DSU
DSU
DSU
DSU
Uniform
Uniform
DSU
DSU
DSU
DSU
Uniform
DSU
DSU
Uniform
Uniform
DSU
DSU
Uniform
...

result:

ok participant made 0 mistakes out of allowed 20

Test #6:

score: 0
Accepted
time: 72ms
memory: 3712kb

input:

10000 50
6602 7794
9813 6808
8567 5704
6649 4641
6456 1453
5197 4343
228 2953
2662 8579
5551 3386
9709 2667
9153 517
4793 5220
2609 9847
9384 2456
1336 1279
4619 1743
2831 3359
7158 8282
1547 981
9756 1792
4580 1348
5853 6360
3112 5599
7364 4224
9372 3236
3282 3821
5748 1939
3053 5570
9492 6541
4873...

output:

DSU
Uniform
DSU
Uniform
DSU
DSU
Uniform
Uniform
Uniform
Uniform
Uniform
Uniform
DSU
Uniform
DSU
DSU
DSU
DSU
Uniform
DSU
Uniform
DSU
Uniform
DSU
DSU
Uniform
Uniform
Uniform
DSU
Uniform
Uniform
DSU
DSU
DSU
DSU
Uniform
Uniform
Uniform
Uniform
DSU
DSU
Uniform
Uniform
DSU
Uniform
Uniform
Uniform
DSU
DSU
...

result:

ok participant made 0 mistakes out of allowed 20

Extra Test:

score: 0
Extra Test Passed