Submission #156100

#	Time	Username	Problem	Language	Result	Execution time	Memory
156100		EntityIT	전압 (JOI14_voltage)	C++14	100 / 100	225 ms	21240 KiB

voltage

#include<bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 5, M = N << 1, inf = (int)1e9 + 123;
int n, m, disc[N], low[N], curDisc, ans, nBadEdge, nBadEdgeTree[N];
bool parity[N], vis[N];
vector<int> gr[N], graph[N];

struct Edge {
    int u, v;
    bool used;
    Edge(int _u = 0, int _v = 0, bool _used = 0) : u(_u), v(_v), used(_used) {}
    int oth(int vertex) { return u ^ v ^ vertex; }
} edge[M];

void dfs(int u, int p) {
    disc[u] = low[u] = ++curDisc;
    parity[u] = parity[p] ^ 1;
    for (int id : gr[u]) if (!edge[id].used) {
        edge[id].used = 1;
        int v = edge[id].oth(u);
        if (!disc[v]) {
            graph[u].emplace_back(v);
            dfs(v, u);
            nBadEdgeTree[u] += nBadEdgeTree[v];
            low[u] = min(low[u], low[v]);
        }
        else {
            if (parity[u] == parity[v]) {
                ++nBadEdge;
                ++nBadEdgeTree[u]; --nBadEdgeTree[v];
            }
            else low[u] = min(low[u], disc[v]);
        }
    }
}

void solve(int u) {
    vis[u] = 1;
    for (int v : graph[u]) {
        solve(v);
        if (low[v] > disc[u] && nBadEdgeTree[v] == nBadEdge) ++ans;
    }
}

int main() {
//    freopen("input", "r", stdin);
    scanf(" %d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf(" %d %d", &u, &v);
        edge[i] = Edge(u, v, 0);
        gr[u].emplace_back(i);
        gr[v].emplace_back(i);
    }

    for (int u = 1; u <= n; ++u) if (!disc[u]) dfs(u, 0);
    if (nBadEdge == 1) ++ans;
    for (int u = 1; u <= n; ++u) if (!vis[u]) solve(u);

    printf("%d", ans);

    return 0;
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~
voltage.cpp:51:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf(" %d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45