QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644615 | #8333. Gift | ACAAA# | WA | 1ms | 6628kb | C++17 | 1.6kb | 2024-10-16 14:48:58 | 2024-10-16 14:48:59 |
Judging History
answer
#include <vector>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
const int N = 100010, M = 1000010;
vector<int>a[N];
bool flag[N];
int path[N],sum,ru[N],chu[N];
int dfs(int x, int pre){
flag[x] = 1;
for (auto v:a[x]){
if (!flag[v]){
int index = dfs(v, x);
if (!index)continue;
if (index != -1)path[++sum] = v;
if (index == v)return -1;
else return index;
}
else if (v != pre){
path[++sum] = v;
return v;
}
}
}
int main(){
int n,ans=0;
cin >> n;
for (int i = 1; i <=n; ++i){
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
chu[u]++;
chu[v]++;
}
int f=0,num=0;
dfs(1, -1);
chu[path[1]]--;
chu[path[2]]--;
for (int i = 1; i <= n; i++) {
if (chu[i] >= 5) {
f = 1;
break;
}
else if (chu[i] >= 4) {
num++;
}
}
if (!f)ans += n - num;
chu[path[2]]++;
chu[path[3]]--;
f = num = 0;
for (int i = 1; i <= n; i++) {
if (chu[i] >= 5) {
f = 1;
break;
}
else if (chu[i] >= 4)
num++;
}
if (!f)ans += n - num;
f = num = 0;
chu[path[1]]++;
chu[path[2]]--;
for (int i = 1; i <= n; i++) {
if (chu[i] >= 5) {
f = 1;
break;
}
else if (chu[i] >= 4)
num++;
}
if (!f)ans += n - num;
cout <<ans<< endl;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5916kb
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: 1ms
memory: 6628kb
input:
3 1 3 3 2 2 1
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 6240kb
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:
6996
result:
wrong answer 1st numbers differ - expected: '5438224', found: '6996'