oj.uz

Submission #156145

# Submission time Handle Problem Language Result Execution time Memory
156145 2019-10-03T16:23:28 Z Flying_dragon_02 전압 (JOI14_voltage) C++14
100 / 100
 242 ms 18028 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 = 2e5 + 5;

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

vector<ii> graph[N];

bool vis[N], used[N];

int cnt;

void dfs(int u, int p) {
    dist[u] = low[u] = ++cnt;
    parity[u] = parity[p] ^ 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i].fi, id = graph[u][i].se;
        if(used[id]) continue;
        used[id] = 1;
        if(!dist[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].fi;
        if(v == p) continue;
        if(!vis[v]) {
            bfs(v, u);
            //cout << u << " " << v << " " << low[v] << " " << dist[u] << "\n";
            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, i});
        graph[v].pb({u, i});
    }
    for(int i = 1; i <= n; i++) {
        if(!dist[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:41: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:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5368 KB Output is correct
2 Correct 7 ms 5240 KB Output is correct
3 Correct 15 ms 5340 KB Output is correct
4 Correct 7 ms 5368 KB Output is correct
5 Correct 7 ms 5368 KB Output is correct
6 Correct 7 ms 5372 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 7 ms 5368 KB Output is correct
9 Correct 7 ms 5368 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5368 KB Output is correct
12 Correct 7 ms 5368 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 10528 KB Output is correct
2 Correct 94 ms 13744 KB Output is correct
3 Correct 56 ms 10560 KB Output is correct
4 Correct 91 ms 14968 KB Output is correct
5 Correct 12 ms 6136 KB Output is correct
6 Correct 85 ms 12664 KB Output is correct
7 Correct 90 ms 16260 KB Output is correct
8 Correct 90 ms 16248 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10476 KB Output is correct
2 Correct 50 ms 16248 KB Output is correct
3 Correct 50 ms 16248 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 63 ms 12536 KB Output is correct
6 Correct 111 ms 10744 KB Output is correct
7 Correct 90 ms 13304 KB Output is correct
8 Correct 99 ms 14292 KB Output is correct
9 Correct 123 ms 14416 KB Output is correct
10 Correct 97 ms 13008 KB Output is correct
11 Correct 74 ms 10644 KB Output is correct
12 Correct 95 ms 12152 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11364 KB Output is correct
2 Correct 86 ms 18028 KB Output is correct
3 Correct 10 ms 6392 KB Output is correct
4 Correct 95 ms 14172 KB Output is correct
5 Correct 82 ms 15224 KB Output is correct
6 Correct 88 ms 13980 KB Output is correct
7 Correct 136 ms 16120 KB Output is correct
8 Correct 199 ms 16348 KB Output is correct
9 Correct 200 ms 14712 KB Output is correct
10 Correct 242 ms 17232 KB Output is correct
11 Correct 204 ms 14840 KB Output is correct
12 Correct 224 ms 17420 KB Output is correct
13 Correct 166 ms 14184 KB Output is correct
14 Correct 154 ms 17700 KB Output is correct
15 Correct 158 ms 17400 KB Output is correct
16 Correct 125 ms 16292 KB Output is correct
17 Correct 139 ms 15096 KB Output is correct
18 Correct 112 ms 14576 KB Output is correct