Submission #544672

#	Time	Username	Problem	Language	Result	Execution time	Memory
544672		pokmui9909	산만한 고양이 (KOI17_cat)	C++17	100 / 100	328 ms	47640 KiB

cat

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int N, M;
vector<int> G[300005];
int tn[300005], bn[300005];
int child[300005];
int cnt = 0;
 
void dfs(int n, int p, bool root)
{
    tn[n] = bn[n] = ++cnt;
    for(auto i : G[n])
    {
        if(i == p) continue;
        if(bn[i])
        {
            bn[n] = min(tn[i], bn[n]);
            continue;
        }
        dfs(i, n, 0);
        bn[n] = min(bn[i], bn[n]);
        if(tn[n] <= bn[i]) child[n]++;
    }
    if(root == 0) child[n]++;
}
 
int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    cin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, -1, 1);
    ll ans = 0;
    for(int i = 1; i <= N; i++)
    {
        if(N - 1 == M - G[i].size() + child[i])
            ans += i;
    }
    cout << ans;
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(N - 1 == M - G[i].size() + child[i])
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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