QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#668933#8333. Gifthuan_yp#TL 0ms0kbC++141.2kb2024-10-23 16:38:472024-10-23 16:38:49

Judging History

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

  • [2024-10-23 16:38:49]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-23 16:38:47]
  • 提交

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

output:


result: