84422024-01-16 13:23:08anonMaximális kaktusz (45 pont)cpp17Wrong answer 38/4530ms12496 KiB
#include <bits/stdc++.h>
#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 nc, rem;
    if(streak >= 3) {
        ans++;
        streak = 0;
    }
    vis[vertex] = true;
    nc = 0;
    for(const auto &x : graph[vertex])
        nc += !vis[x];
    vector<ll> rs;
    for(const auto &x : graph[vertex]) {
        if(vis[x])
            continue;
        rem = dfs(x, 1 + (nc == 1) * streak, ans, vis, graph);
        if(nc == 1)
            return rem;
        else if(rem)
            rs.push_back(rem);
    }
    if(rs.size() == 1) {
        if(streak + rs[0] >= 3)
            ans++;
        return (streak + rs[0]) % 3;
    }
    if(nc >= 2 && rs.size() >= 2 && streak) {
        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;
}
SubtaskSumTestVerdictTimeMemory
base38/45
1Accepted0/03ms2232 KiB
2Accepted0/03ms2432 KiB
3Accepted1/13ms2368 KiB
4Accepted1/13ms2580 KiB
5Accepted1/13ms2796 KiB
6Accepted2/23ms2928 KiB
7Accepted2/23ms3064 KiB
8Accepted2/22ms2980 KiB
9Accepted1/13ms3112 KiB
10Accepted1/13ms3344 KiB
11Wrong answer0/13ms3588 KiB
12Accepted1/13ms3672 KiB
13Accepted1/13ms3848 KiB
14Accepted1/13ms3944 KiB
15Wrong answer0/13ms4316 KiB
16Accepted1/13ms4528 KiB
17Wrong answer0/13ms4556 KiB
18Wrong answer0/129ms10508 KiB
19Accepted1/126ms11028 KiB
20Wrong answer0/130ms10568 KiB
21Wrong answer0/130ms10568 KiB
22Accepted2/221ms12156 KiB
23Accepted2/221ms12108 KiB
24Accepted2/221ms12160 KiB
25Accepted2/221ms12292 KiB
26Accepted1/13ms4612 KiB
27Accepted1/13ms4864 KiB
28Wrong answer0/13ms4932 KiB
29Accepted1/126ms12496 KiB
30Accepted1/127ms11896 KiB
31Accepted1/124ms12228 KiB
32Accepted1/125ms12340 KiB
33Accepted2/226ms12448 KiB
34Accepted2/226ms12316 KiB
35Accepted2/224ms12332 KiB
36Accepted2/224ms12312 KiB