84522024-01-16 16:23:06anonMaximális kaktusz (45 pont)cpp17Wrong answer 38/4532ms12064 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 rem;
    if(streak >= 3) {
        ans++;
        streak = 0;
    }
    vis[vertex] = true;
    vector<ll> nbs;
    vector<ll> rs;
    for(const auto &x : graph[vertex]) {
        if(!vis[x])
            nbs.push_back(x);
    }
    if(nbs.size() == 1)
        return dfs(nbs[0], streak + 1, ans, vis, graph);
    else if(nbs.size() >= 2) {
        for(const auto &x : nbs) {
            rem = dfs(x, 1, ans, vis, graph);
            if(rem)
                rs.push_back(rem);
        }
        if(rs.size() == 1) {
            ans += (streak + rs[0]) / 3;
            return (streak + rs[0]) % 3;
        }
        else if(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/03ms2108 KiB
2Accepted0/03ms2476 KiB
3Accepted1/13ms2516 KiB
4Accepted1/13ms2552 KiB
5Accepted1/13ms2644 KiB
6Accepted2/23ms2840 KiB
7Accepted2/22ms2924 KiB
8Accepted2/22ms2920 KiB
9Accepted1/13ms3052 KiB
10Accepted1/13ms3060 KiB
11Wrong answer0/13ms3060 KiB
12Accepted1/13ms3192 KiB
13Accepted1/13ms3404 KiB
14Accepted1/13ms3480 KiB
15Wrong answer0/13ms3540 KiB
16Accepted1/13ms3540 KiB
17Wrong answer0/13ms3544 KiB
18Wrong answer0/130ms9492 KiB
19Accepted1/125ms9876 KiB
20Wrong answer0/132ms9492 KiB
21Wrong answer0/132ms9488 KiB
22Accepted2/221ms11720 KiB
23Accepted2/221ms11720 KiB
24Accepted2/221ms11828 KiB
25Accepted2/221ms11712 KiB
26Accepted1/13ms3624 KiB
27Accepted1/13ms3476 KiB
28Wrong answer0/13ms3540 KiB
29Accepted1/126ms11716 KiB
30Accepted1/126ms11068 KiB
31Accepted1/128ms11852 KiB
32Accepted1/125ms12064 KiB
33Accepted2/226ms11944 KiB
34Accepted2/225ms11776 KiB
35Accepted2/223ms12060 KiB
36Accepted2/223ms11984 KiB