oj.uz

Submission #658892

# Submission time Handle Problem Language Result Execution time Memory
658892 2022-11-15T11:26:57 Z JooDdae None (KOI17_cat) C++17
23 / 100
 408 ms 88848 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);
    if(bcc.size() > 1) return cout << "0\n", 0;

    set<int> s;
    for(auto b : bcc) for(auto [x, y] : b) s.insert(x), s.insert(y);

    ll ans = 0;
    for(int i=1;i<=n;i++) if(m-(int)v[i].size() == n-2 && (bcc.empty() || (s.count(i) && !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 4 ms 7384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 37352 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 220 ms 88840 KB Output is correct
2 Correct 211 ms 88764 KB Output is correct
3 Correct 218 ms 88804 KB Output is correct
4 Correct 223 ms 88848 KB Output is correct
5 Correct 212 ms 88784 KB Output is correct
6 Correct 240 ms 88788 KB Output is correct
7 Correct 217 ms 88848 KB Output is correct
8 Correct 209 ms 88696 KB Output is correct
9 Correct 212 ms 88692 KB Output is correct
10 Correct 187 ms 76856 KB Output is correct
11 Correct 181 ms 76804 KB Output is correct
12 Correct 175 ms 76800 KB Output is correct
13 Correct 183 ms 76832 KB Output is correct
14 Correct 186 ms 76796 KB Output is correct
15 Correct 182 ms 64752 KB Output is correct
16 Correct 172 ms 64636 KB Output is correct
17 Correct 181 ms 64860 KB Output is correct
18 Correct 173 ms 64736 KB Output is correct
19 Correct 182 ms 64768 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 4 ms 7384 KB Output isn't correct
4 Halted 0 ms 0 KB -