oj.uz

Submission #658899

# Submission time Handle Problem Language Result Execution time Memory
658899 2022-11-15T11:47:54 Z JooDdae None (KOI17_cat) C++17
33 / 100
 272 ms 86160 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 c[300300];

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

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

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

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:53:80: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=1;i<=n;i++) if(m-(int)v[i].size() <= n-2 && (bcc.empty() || c[i] == bcc.size())) ans += i;
      |                                                                           ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Incorrect 5 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 236 ms 19440 KB Output is correct
2 Correct 211 ms 19524 KB Output is correct
3 Correct 198 ms 19532 KB Output is correct
4 Correct 207 ms 19588 KB Output is correct
5 Correct 211 ms 19536 KB Output is correct
6 Correct 209 ms 20532 KB Output is correct
7 Correct 199 ms 20424 KB Output is correct
8 Correct 205 ms 20420 KB Output is correct
9 Correct 235 ms 20172 KB Output is correct
10 Correct 244 ms 20648 KB Output is correct
11 Correct 212 ms 21572 KB Output is correct
12 Correct 209 ms 22024 KB Output is correct
13 Correct 240 ms 21136 KB Output is correct
14 Correct 207 ms 20936 KB Output is correct
15 Correct 218 ms 22216 KB Output is correct
16 Correct 267 ms 33240 KB Output is correct
17 Correct 220 ms 35404 KB Output is correct
18 Correct 206 ms 29244 KB Output is correct
19 Correct 272 ms 35092 KB Output is correct
20 Correct 217 ms 31164 KB Output is correct
21 Correct 222 ms 26532 KB Output is correct
22 Correct 227 ms 46048 KB Output is correct
23 Correct 204 ms 51380 KB Output is correct
24 Correct 222 ms 27300 KB Output is correct
25 Correct 236 ms 51800 KB Output is correct
26 Correct 212 ms 85984 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 85964 KB Output is correct
2 Correct 228 ms 86012 KB Output is correct
3 Correct 232 ms 86072 KB Output is correct
4 Correct 265 ms 86036 KB Output is correct
5 Correct 227 ms 86080 KB Output is correct
6 Correct 217 ms 86160 KB Output is correct
7 Correct 231 ms 85996 KB Output is correct
8 Correct 211 ms 85960 KB Output is correct
9 Correct 231 ms 86012 KB Output is correct
10 Correct 182 ms 73900 KB Output is correct
11 Correct 185 ms 73932 KB Output is correct
12 Correct 206 ms 73860 KB Output is correct
13 Correct 186 ms 73952 KB Output is correct
14 Correct 188 ms 73860 KB Output is correct
15 Correct 188 ms 61792 KB Output is correct
16 Correct 183 ms 61808 KB Output is correct
17 Correct 181 ms 61752 KB Output is correct
18 Correct 174 ms 61836 KB Output is correct
19 Correct 188 ms 61800 KB Output is correct

Subtask #4
0 / 55.0

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