oj.uz

Submission #156140

# Submission time Handle Problem Language Result Execution time Memory
156140 2019-10-03T16:11:02 Z Flying_dragon_02 전압 (JOI14_voltage) C++14
55 / 100
 1000 ms 39988 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;

map<ii, int> mymap;

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 {
                if(v == p && mymap[{u, v}] >= 2)
                    low[u] = min(low[u], dist[v]);
                else if(v != p)
                    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);
        mymap[{u, v}]++;
        mymap[{v, u}]++;
        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:44: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:71: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 6 ms 3192 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 5 ms 2936 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 7 ms 3192 KB Output is correct
7 Correct 7 ms 3192 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 6 ms 3064 KB Output is correct
10 Correct 7 ms 3192 KB Output is correct
11 Correct 4 ms 3260 KB Output is correct
12 Correct 7 ms 3192 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 20064 KB Output is correct
2 Correct 404 ms 25476 KB Output is correct
3 Correct 283 ms 20032 KB Output is correct
4 Correct 411 ms 27404 KB Output is correct
5 Correct 32 ms 5240 KB Output is correct
6 Correct 528 ms 23232 KB Output is correct
7 Correct 491 ms 29528 KB Output is correct
8 Correct 425 ms 29560 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 19948 KB Output is correct
2 Correct 152 ms 29352 KB Output is correct
3 Correct 147 ms 29432 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 284 ms 21340 KB Output is correct
6 Correct 353 ms 19960 KB Output is correct
7 Correct 446 ms 24360 KB Output is correct
8 Correct 539 ms 26504 KB Output is correct
9 Correct 554 ms 25820 KB Output is correct
10 Correct 553 ms 24012 KB Output is correct
11 Correct 505 ms 20328 KB Output is correct
12 Correct 520 ms 22604 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 20440 KB Output is correct
2 Correct 265 ms 29432 KB Output is correct
3 Correct 7 ms 3960 KB Output is correct
4 Correct 555 ms 26620 KB Output is correct
5 Correct 449 ms 28108 KB Output is correct
6 Correct 414 ms 26288 KB Output is correct
7 Correct 727 ms 36856 KB Output is correct
8 Correct 737 ms 38492 KB Output is correct
9 Correct 744 ms 36288 KB Output is correct
10 Correct 759 ms 39988 KB Output is correct
11 Execution timed out 1046 ms 34340 KB Time limit exceeded
12 Halted 0 ms 0 KB -