oj.uz

Submission #658898

# Submission time Handle Problem Language Result Execution time Memory
658898 2022-11-15T11:41:56 Z JooDdae None (KOI17_cat) C++17
33 / 100
 254 ms 84864 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(m-(int)v[i].size() <= n-2 && (bcc.empty() || s.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 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 19372 KB Output is correct
2 Correct 208 ms 19404 KB Output is correct
3 Correct 230 ms 19324 KB Output is correct
4 Correct 230 ms 19516 KB Output is correct
5 Correct 205 ms 19436 KB Output is correct
6 Correct 229 ms 19700 KB Output is correct
7 Correct 209 ms 19580 KB Output is correct
8 Correct 202 ms 19476 KB Output is correct
9 Correct 210 ms 19568 KB Output is correct
10 Correct 226 ms 19588 KB Output is correct
11 Correct 214 ms 20612 KB Output is correct
12 Correct 209 ms 20888 KB Output is correct
13 Correct 237 ms 20480 KB Output is correct
14 Correct 213 ms 20656 KB Output is correct
15 Correct 209 ms 20956 KB Output is correct
16 Correct 220 ms 32156 KB Output is correct
17 Correct 228 ms 34232 KB Output is correct
18 Correct 207 ms 28152 KB Output is correct
19 Correct 241 ms 33980 KB Output is correct
20 Correct 233 ms 29928 KB Output is correct
21 Correct 213 ms 25284 KB Output is correct
22 Correct 227 ms 44904 KB Output is correct
23 Correct 200 ms 50208 KB Output is correct
24 Correct 243 ms 26056 KB Output is correct
25 Correct 254 ms 50548 KB Output is correct
26 Correct 223 ms 84864 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 84852 KB Output is correct
2 Correct 210 ms 84864 KB Output is correct
3 Correct 214 ms 84800 KB Output is correct
4 Correct 214 ms 84800 KB Output is correct
5 Correct 212 ms 84864 KB Output is correct
6 Correct 204 ms 84860 KB Output is correct
7 Correct 227 ms 84788 KB Output is correct
8 Correct 209 ms 84860 KB Output is correct
9 Correct 209 ms 84828 KB Output is correct
10 Correct 177 ms 72964 KB Output is correct
11 Correct 179 ms 72864 KB Output is correct
12 Correct 185 ms 72860 KB Output is correct
13 Correct 175 ms 72888 KB Output is correct
14 Correct 199 ms 73240 KB Output is correct
15 Correct 208 ms 60964 KB Output is correct
16 Correct 172 ms 60936 KB Output is correct
17 Correct 184 ms 61036 KB Output is correct
18 Correct 192 ms 61028 KB Output is correct
19 Correct 179 ms 60916 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 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -