Submission #131542

#	Time	Username	Problem	Language	Result	Execution time	Memory
131542		dndhk	산만한 고양이 (KOI17_cat)	C++14	100 / 100	460 ms	40056 KiB

cat

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 300000;

int N, M;
vector<int> gp[MAX_N+1];
int lv[MAX_N+1], p[MAX_N+1], C[MAX_N+1], up[MAX_N+1];
bool vst[MAX_N+1];
bool chk[MAX_N+1];
ll ans;

void dfs(int x){
    vst[x] = chk[x] = true;
    for(int i=0; i<gp[x].size(); i++){
        if(gp[x][i]==p[x])  continue;
        if(vst[gp[x][i]]){
            if(lv[x]>lv[gp[x][i]]){C[x]++; up[gp[x][i]]++;}
            continue;
        }
        lv[gp[x][i]] = lv[x]+1;  p[gp[x][i]] = x;  
        dfs(gp[x][i]);  C[x] += C[gp[x][i]]; 
        if(C[gp[x][i]] - up[x] > 1) chk[x] = false;
        if(up[x]>0)    chk[p[x]] = false;
        up[p[x]]+=up[x]; up[x] = 0;
    }
    if(chk[x] && C[x]==M)    ans+=(ll)x;
}


int main(){
    scanf("%d%d", &N, &M);
    for(int i=0; i<M; i++){
        int a, b; scanf("%d%d", &a, &b);
        gp[a].pb(b); gp[b].pb(a);
    }
    M -= (N-1);
    lv[1] = 1; dfs(1);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

cat.cpp: In function 'void dfs(int)':
cat.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gp[x].size(); i++){
                  ~^~~~~~~~~~~~~
cat.cpp: In function 'int main()':
cat.cpp:52: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:54: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