8461 2024. 01. 16 20:57:29 anon Maximális kaktusz (45 pont) cpp17 Elfogadva 45/45 34ms 12692 KiB 
#include <bits/stdc++.h>
#define HANDLE_STREAK \
    if(streak >= 3) { \
        ans++; \
        streak = 0; \
    }
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
ll remove_cycles(ll vertex, ll parent, vector<bool> &bad_nodes, vector<bool> &vis, const vector<vector<ll>> &graph) {
    ll detected, result;
    if(vis[vertex]) {
        bad_nodes[vertex] = true;
        return vertex;
    }
    vis[vertex] = true;
    result = 0;
    for(const auto &x : graph[vertex]) {
        if(x == parent || bad_nodes[x])
            continue;
        detected = remove_cycles(x, vertex, bad_nodes, vis, graph);
        if(detected) {
            bad_nodes[vertex] = true;
            if(detected != vertex)
                result = detected;
        }
    }
    return result;
}
ll dfs(ll vertex, ll streak, ll &ans, vector<bool> &vis, const vector<vector<ll>> &graph) {
    ll rem;
    vis[vertex] = true;
    vector<ll> nbs;
    for(const auto &x : graph[vertex]) {
        if(!vis[x])
            nbs.push_back(x);
    }
    if(nbs.empty()) {
        HANDLE_STREAK;
        return streak;
    }
    else if(nbs.size() == 1) {
        HANDLE_STREAK;
        return dfs(nbs[0], streak + 1, ans, vis, graph);
    }
    else if(nbs.size() >= 2) {
        vector<ll> rs;
        for(const auto &x : nbs) {
            rem = dfs(x, 1, ans, vis, graph);
            if(rem)
                rs.push_back(rem);
        }
        if(rs.empty()) {
            HANDLE_STREAK;
            return streak;
        }
        else if(rs.size() == 1) {
            HANDLE_STREAK;
            ans += (streak + rs[0]) / 3;
            return (streak + rs[0]) % 3;
        }
        else if(rs.size() >= 2) {
            ans++;
            return streak - 1;
        }
    }
    return streak;
}
int main() {
    FastIO;
    ll i, u, v, ans, N, M;
    cin >> N >> M;
    vector<vector<ll>> graph(N + 1);
    for(i = 0; i < M; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<bool> vis(N + 1, false);
    vector<bool> bad_nodes(N + 1, false);
    remove_cycles(1, -1, bad_nodes, vis, graph);
    ans = 0;
    for(i = 1; i <= N; i++) {
        if(!bad_nodes[i])
            dfs(i, 1, ans, bad_nodes, graph);
    }
    cout << ans << '\n';
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 45/45
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 3ms 2220 KiB
3 Elfogadva 1/1 3ms 2268 KiB
4 Elfogadva 1/1 3ms 2484 KiB
5 Elfogadva 1/1 3ms 2568 KiB
6 Elfogadva 2/2 3ms 2692 KiB
7 Elfogadva 2/2 3ms 2944 KiB
8 Elfogadva 2/2 3ms 2920 KiB
9 Elfogadva 1/1 3ms 3124 KiB
10 Elfogadva 1/1 3ms 3204 KiB
11 Elfogadva 1/1 3ms 3296 KiB
12 Elfogadva 1/1 3ms 3296 KiB
13 Elfogadva 1/1 3ms 3428 KiB
14 Elfogadva 1/1 3ms 3612 KiB
15 Elfogadva 1/1 3ms 3740 KiB
16 Elfogadva 1/1 3ms 3648 KiB
17 Elfogadva 1/1 3ms 3936 KiB
18 Elfogadva 1/1 32ms 9884 KiB
19 Elfogadva 1/1 26ms 10200 KiB
20 Elfogadva 1/1 34ms 9808 KiB
21 Elfogadva 1/1 32ms 9912 KiB
22 Elfogadva 2/2 28ms 12268 KiB
23 Elfogadva 2/2 23ms 12080 KiB
24 Elfogadva 2/2 21ms 12300 KiB
25 Elfogadva 2/2 21ms 12372 KiB
26 Elfogadva 1/1 3ms 4184 KiB
27 Elfogadva 1/1 3ms 4244 KiB
28 Elfogadva 1/1 3ms 4448 KiB
29 Elfogadva 1/1 27ms 12492 KiB
30 Elfogadva 1/1 26ms 12180 KiB
31 Elfogadva 1/1 26ms 12668 KiB
32 Elfogadva 1/1 25ms 12672 KiB
33 Elfogadva 2/2 27ms 12692 KiB
34 Elfogadva 2/2 27ms 12536 KiB
35 Elfogadva 2/2 24ms 12672 KiB
36 Elfogadva 2/2 24ms 12668 KiB