oj.uz

Submission #156142

# Submission time Handle Problem Language Result Execution time Memory
156142 2019-10-03T16:15:04 Z Flying_dragon_02 전압 (JOI14_voltage) C++11
0 / 100
 76 ms 13780 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e9;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

const int N = 1e5 + 5;

int n, m, bad[N], badEdge, ans, parity[N], dist[N], low[N];

vector<int> graph[N];

bool vis[N];

int cnt;

void dfs(int u, int p) {
    dist[u] = low[u] = ++cnt;
    vis[u] = 1;
    parity[u] = parity[p] ^ 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(!vis[v]) {
            dfs(v, u);
            bad[u] += bad[v];
            low[u] = min(low[u], low[v]);
        }
        else {
            if(parity[v] == parity[u]) {
                if(dist[v] < dist[u]) {
                    bad[v]--;
                    bad[u]++;
                    badEdge++;
                }
            }
            else
                low[u] = min(low[u], dist[v]);
        }
    }
}

void bfs(int u, int p) {
    vis[u] = 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(v == p) continue;
        if(!vis[v]) {
            bfs(v, u);
            if(bad[v] == badEdge && low[v] > dist[u])
            ans++;
        }
    }
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i])
            dfs(i, i);
    }
    if(badEdge == 1)
        ans++;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) {
        if(!vis[i])
            bfs(i, i);
    }
    cout << ans;
}

Compilation message

voltage.cpp: In function 'void dfs(int, int)':
voltage.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
voltage.cpp: In function 'void bfs(int, int)':
voltage.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8020 KB Output is correct
2 Correct 76 ms 13780 KB Output is correct
3 Incorrect 6 ms 3960 KB Output isn't correct
4 Halted 0 ms 0 KB -