QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668933 | #8333. Gift | huan_yp# | TL | 0ms | 0kb | C++14 | 1.2kb | 2024-10-23 16:38:47 | 2024-10-23 16:38:49 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> e[N];
int fa[N], deg[N], cnt[10];
vector<int> cycle;
void dfs(int u){
for(auto v:e[u]){
if(v==fa[u])continue;
if(fa[v]!=-1){
int x=u;
cycle.push_back(v);
while(x!=v){
cycle.push_back(x);
x=fa[x];
}
continue;
}
fa[v]=u;
dfs(v);
}
}
int main(){
int n;
cin>>n;
memset(fa,-1,sizeof(fa));
fa[1]=0;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
deg[x]++,deg[y]++;
e[x].push_back(y),e[y].push_back(x);
}
dfs(1);
long long ans=0;
for(int i=1;i<=n;i++){
cnt[deg[i]]++;
}
cycle.push_back(cycle[0]);
for(int i=0; i<cycle.size()-1; i++){
int u=cycle[i], v=cycle[i+1];
cnt[deg[u]]--, cnt[deg[v]]--;
cnt[deg[u]-1]++, cnt[deg[v]-1]++;
if(cnt[5]==0){
ans += cnt[3] + cnt[2] + cnt[1];
}
cnt[deg[u]-1]--, cnt[deg[v]-1]--;
cnt[deg[u]]++, cnt[deg[v]]++;
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
6 1 2 1 3 1 4 1 5 1 6 2 3