QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#701156 | #8333. Gift | XiCen# | WA | 103ms | 30888kb | C++14 | 2.0kb | 2024-11-02 13:50:35 | 2024-11-02 13:50:53 |
Judging History
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'