QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#701156#8333. GiftXiCen#WA 103ms30888kbC++142.0kb2024-11-02 13:50:352024-11-02 13:50:53

Judging History

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

  • [2024-11-02 13:50:53]
  • 评测
  • 测评结果:WA
  • 用时:103ms
  • 内存:30888kb
  • [2024-11-02 13:50:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)2e5 + 5
#define pdd pair<double, double>
#define pii pair<int, int>

int a, b, c, d, x, y, n, m, t, k, q, l, r, p, z, h;
int num[N], in[N];
int cnt[N];
stack<int> st;
string s;
map<int, int> mp;
int f = 0;
vector<int> g[N];
pii edge[N];
void dfs(int now, int fa) {
    if (f) return;
    if (in[now]) {
        do {
            y = st.top();
            st.pop();
            mp[y] = 1;
        } while (y != now);
        f = 1;
        return;
    }
    in[now] = 1;
    st.push(now);
    for (auto &i : g[now]) {
        if (i != fa)
            dfs(i, now);
    }
    in[now] = 0;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	// 注意根据数据量调整N的大小
    cin >> n;
//    cout << edge[0].first << ' ' << edge[1].second << '\n';
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
        edge[i] = {x, y};
        cnt[x]++;
        cnt[y]++;
    }
    dfs(1, 0);
//    for (auto it = mp.begin(); it != mp.end(); it++) {
//        cout << it->first << '\n';
//    }
    int c5, c3;
    c5 = c3 = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] >= 5) c5++;
        else if (cnt[i] <= 3) c3++;
    }
//    cout << c3 << ' ' << c5 << '\n';
    int ans = 0;
    for (int j = 1; j <= n; j++) {
        pii i = edge[j];
        int c55 = c5, c33 = c3;
        if (!mp.count(i.first) || !mp.count(i.second)) continue;
        if (cnt[i.first]>=5&&cnt[i.first]-1<5) c55--;
        else if (cnt[i.first]>3&&cnt[i.first]-1<=3) c33++;

        if (cnt[i.second]>=5&&cnt[i.second]-1<5) c55--;
        else if (cnt[i.second]>3&&cnt[i.second]-1<=3) c33++;

//        cout << i.first << ' ' << i.second << ' ' << c3 << ' ' << c5 << '\n';

        if (!c55) ans += c33;
    }
    if (n == 2) {
        cout << 4 << '\n';
    } else cout << ans << '\n';
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9788kb

input:

6
1 2
1 3
1 4
1 5
1 6
2 3

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: 0
Accepted
time: 0ms
memory: 12036kb

input:

3
1 3
3 2
2 1

output:

9

result:

ok 1 number(s): "9"

Test #3:

score: 0
Accepted
time: 3ms
memory: 10180kb

input:

2332
1648 909
1676 2122
1644 1981
1106 1131
1785 239
223 618
335 1662
424 1775
889 1684
1589 52
1406 1747
1600 302
790 2056
1742 464
1706 541
1145 779
2316 833
1645 1439
859 438
1337 136
746 1565
436 1730
2079 2145
1583 1940
917 1549
1863 507
1266 367
1890 2230
13 2113
492 2109
120 1122
815 1111
134...

output:

5438224

result:

ok 1 number(s): "5438224"

Test #4:

score: 0
Accepted
time: 103ms
memory: 30888kb

input:

100000
46198 33056
80285 88339
88963 925
43203 66233
13618 35880
19864 76475
90021 73072
3202 63653
41571 83067
22067 98768
10753 16653
32856 85797
3483 2064
46659 9486
23290 82179
97966 23617
81566 7334
81774 76138
10959 75816
93471 12058
97260 66262
85541 78476
67864 87220
8607 52245
38957 67603
7...

output:

10000000000

result:

ok 1 number(s): "10000000000"

Test #5:

score: 0
Accepted
time: 64ms
memory: 23708kb

input:

100000
54772 14057
70680 93042
84913 63248
79360 97774
84190 60881
31137 29439
99037 81117
38579 32074
31206 19912
70774 23067
60717 79586
83847 43306
55351 50174
32566 70092
22736 92279
55916 20029
41571 63309
33143 65579
35033 3869
50038 4275
59533 25348
53092 32698
27604 14678
6802 18226
23173 96...

output:

5017400000

result:

ok 1 number(s): "5017400000"

Test #6:

score: 0
Accepted
time: 35ms
memory: 17800kb

input:

50000
26768 20197
5956 49805
44024 45008
29783 4843
7173 42904
36329 3666
1258 35410
1245 42591
41226 20145
41177 25916
38397 36431
3822 43842
414 31694
28969 33316
47036 42639
5433 1631
26813 16959
17557 18806
45146 10231
26867 24805
4416 45505
44772 32136
26263 17264
43426 20507
26630 4199
9781 89...

output:

94055

result:

ok 1 number(s): "94055"

Test #7:

score: -100
Wrong Answer
time: 18ms
memory: 15128kb

input:

50000
17715 45957
32674 24013
11618 34470
40375 26273
42845 13128
47455 22000
32874 30876
17491 31661
34844 19762
9072 37619
36110 709
268 34175
4270 20690
29515 33513
27912 43001
45583 31336
47547 28782
26922 36614
28304 10847
34444 24189
22768 40293
20188 44360
15389 17250
1073 12635
2478 47836
13...

output:

341694418

result:

wrong answer 1st numbers differ - expected: '8051734', found: '341694418'