oj.uz

Submission #658893

# Submission time Handle Problem Language Result Execution time Memory
658893 2022-11-15T11:28:33 Z JooDdae None (KOI17_cat) C++17
23 / 100
 459 ms 84904 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() || !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 3 ms 7380 KB Output is correct
3 Incorrect 4 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 459 ms 33448 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 208 ms 84904 KB Output is correct
2 Correct 214 ms 84840 KB Output is correct
3 Correct 234 ms 84788 KB Output is correct
4 Correct 222 ms 84800 KB Output is correct
5 Correct 229 ms 84860 KB Output is correct
6 Correct 226 ms 84872 KB Output is correct
7 Correct 266 ms 84904 KB Output is correct
8 Correct 222 ms 84904 KB Output is correct
9 Correct 218 ms 84844 KB Output is correct
10 Correct 186 ms 72944 KB Output is correct
11 Correct 182 ms 72852 KB Output is correct
12 Correct 196 ms 72908 KB Output is correct
13 Correct 185 ms 72984 KB Output is correct
14 Correct 210 ms 72940 KB Output is correct
15 Correct 199 ms 60984 KB Output is correct
16 Correct 182 ms 61156 KB Output is correct
17 Correct 180 ms 60928 KB Output is correct
18 Correct 179 ms 60964 KB Output is correct
19 Correct 206 ms 61052 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 3 ms 7380 KB Output is correct
3 Incorrect 4 ms 7380 KB Output isn't correct
4 Halted 0 ms 0 KB -