oj.uz

Submission #658897

# Submission time Handle Problem Language Result Execution time Memory
658897 2022-11-15T11:40:08 Z JooDdae None (KOI17_cat) C++17
10 / 100
 253 ms 88752 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;

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);
            }
        }
    }

    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(bcc.empty() || s.count(i)) ans += i;
    cout << ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 19428 KB Output is correct
2 Correct 232 ms 23440 KB Output is correct
3 Correct 226 ms 23336 KB Output is correct
4 Correct 230 ms 23304 KB Output is correct
5 Correct 215 ms 23372 KB Output is correct
6 Correct 250 ms 23448 KB Output is correct
7 Correct 234 ms 23440 KB Output is correct
8 Correct 241 ms 23436 KB Output is correct
9 Correct 219 ms 23404 KB Output is correct
10 Correct 215 ms 23496 KB Output is correct
11 Correct 213 ms 24508 KB Output is correct
12 Correct 206 ms 24784 KB Output is correct
13 Correct 220 ms 24472 KB Output is correct
14 Correct 205 ms 24636 KB Output is correct
15 Correct 227 ms 24908 KB Output is correct
16 Correct 226 ms 36000 KB Output is correct
17 Correct 252 ms 38156 KB Output is correct
18 Correct 200 ms 31908 KB Output is correct
19 Correct 238 ms 37788 KB Output is correct
20 Correct 244 ms 33980 KB Output is correct
21 Correct 216 ms 29244 KB Output is correct
22 Correct 225 ms 48772 KB Output is correct
23 Correct 202 ms 54288 KB Output is correct
24 Correct 214 ms 29948 KB Output is correct
25 Correct 228 ms 54500 KB Output is correct
26 Correct 253 ms 88752 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 55.0

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