QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735543 | #8333. Gift | qikala7777# | WA | 2ms | 5776kb | C++23 | 2.0kb | 2024-11-11 20:36:14 | 2024-11-11 20:36:15 |
Judging History
answer
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef tuple<int,LL,LL> TPL;
typedef pair<LL,LL> PII;
const int N=1e6+7,inf=0x3f3f3f3f;const LL Linf=0x3f3f3f3f3f3f3f3fLL;
LL qsm(LL a,LL b,LL p){LL res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
LL lowbit(LL x){return x&-x;}
int n;
vector<int>g[N];
int du[N];
bool st[N];
void solve(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)du[i]=g[i].size();
queue<int>q;
for(int i=1;i<=n;i++){
if(du[i]==1)q.push(i);
}
while(q.size()){
int u=q.front();q.pop();
for(auto v:g[u]){
du[v]--;
if(du[v]==1)q.push(v);
}
}
int hcnt=0;
for(int i=1;i<=n;i++){
if(du[i]>1){
st[i]=1;
hcnt++;
}
}
int cnt=0;
set<int>aa;
for(int i=1;i<=n;i++){
if(g[i].size()==4){
cnt++;
}else if(g[i].size()==5){
aa.insert(i);
}
}
LL sum=0;
for(int i=1;i<=n;i++){
if(g[i].size()>3)continue;
for(auto v:g[i]){
if(g[v].size()==5){
if(st[i]){
sum++;
}else{
sum+=2;
}
}else if(g[v].size()==4){
if(aa.size())continue;
if(st[i]&&st[v]){
sum+=hcnt-2;
}else{
sum+=hcnt-1;
}
}else{
if(aa.size())continue;
if(st[i]&&st[v]){
sum+=hcnt-2;
}else{
sum+=hcnt-1;
}
}
}
}
cout<<sum<<endl;
}
int main(){
IOS
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5776kb
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: -100
Wrong Answer
time: 2ms
memory: 5632kb
input:
3 1 3 3 2 2 1
output:
-4
result:
wrong answer 1st numbers differ - expected: '9', found: '-4'