oj.uz

Submission #658894

# Submission time Handle Problem Language Result Execution time Memory
658894 2022-11-15T11:28:47 Z JooDdae None (KOI17_cat) C++17
23 / 100
 427 ms 73356 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;

int in[300200], low[300200], cnt;
vector<int> v[300200];
stack<pair<int, int>> st;
vector<vector<pair<int, int>>> bcc;
set<int> ns;

int dfs(int u, int p){
    in[u] = low[u] = ++cnt;

    for(auto x : v[u]) if(x != p){
        if(in[u] > in[x]) st.push({u, x});

        if(in[x]) low[u] = min(low[u], in[x]);
        else{
            low[u] = min(low[u], dfs(x, u));
            if(low[x] >= in[u]){
                vector<pair<int, int>> b;
                while(st.top() != make_pair(u, x)) b.push_back(st.top()), st.pop();
                b.push_back(st.top()), st.pop();
                if(b.size() > 1) bcc.push_back(b);
                else ns.insert(b[0].first), ns.insert(b[0].second);
            }
        }
    }

    return low[u];
}


int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int a, b; cin >> a >> b;
        v[a].push_back(b), v[b].push_back(a);
    }

    dfs(1, 0);

    ll ans = 0;
    for(int i=1;i<=n;i++) if(m-(int)v[i].size() == n-2 && (bcc.empty() || !ns.count(i))) ans += i;
    cout << ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Incorrect 5 ms 7380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 427 ms 33568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 73356 KB Output is correct
2 Correct 106 ms 73336 KB Output is correct
3 Correct 102 ms 73340 KB Output is correct
4 Correct 105 ms 73272 KB Output is correct
5 Correct 110 ms 73300 KB Output is correct
6 Correct 106 ms 73340 KB Output is correct
7 Correct 104 ms 73312 KB Output is correct
8 Correct 137 ms 73356 KB Output is correct
9 Correct 106 ms 73328 KB Output is correct
10 Correct 135 ms 63800 KB Output is correct
11 Correct 119 ms 63748 KB Output is correct
12 Correct 114 ms 63684 KB Output is correct
13 Correct 113 ms 63676 KB Output is correct
14 Correct 140 ms 63660 KB Output is correct
15 Correct 121 ms 54200 KB Output is correct
16 Correct 121 ms 54188 KB Output is correct
17 Correct 121 ms 54096 KB Output is correct
18 Correct 120 ms 54204 KB Output is correct
19 Correct 128 ms 54184 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Incorrect 5 ms 7380 KB Output isn't correct
4 Halted 0 ms 0 KB -