Submission #124491

#	Time	Username	Problem	Language	Result	Execution time	Memory
124491		DJ035	산만한 고양이 (KOI17_cat)	C++14	100 / 100	571 ms	70064 KiB

cat

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define pb push_back
typedef long long lld;
int N, M, C;
int dep[MAXN];
int U[MAXN], D[MAXN], F[MAXN];
vector <int> con[MAXN], child[MAXN];
void dfs(int n, int from)
{
    for (int t: con[n]) if (t != from){
        if (!dep[t]){
            child[n].pb(t); dep[t] = dep[n]+1;
            int tmp = U[n]; dfs(t, n); F[t] = U[n]-tmp;
            U[n] += U[t]; D[n] += D[t];
        }else if (dep[t] < dep[n]){
            D[n]++; U[t]++;
        }
    }
}
int main()
{
    scanf("%d%d", &N, &M);
    for (int i=1;i<=M;i++){
        int a, b; scanf("%d%d", &a, &b);
        con[a].pb(b); con[b].pb(a);
    }
    dep[1] = 1; dfs(1, 0);
 
    lld ans = 0;
    for (int i=1;i<=N;i++){
        bool skip = 0;
        for (int t: child[i])
            if (D[t]-F[t] > 1 || U[t]) skip = 1;
        if (skip || M-(N-1)-D[i] != 0) continue;
        ans += i;
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
cat.cpp:26:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d%d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 55 / 55