Submission #1148738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148738		andrejikus	전압 (JOI14_voltage)	C++20	0 / 100	132 ms	23484 KiB

voltage

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 2e5 + 3;
vector<int> adj[N];
bool vis[N];
int crv[N], indeg[N];
bool nasao;
bool cyc[N];
int n, m;
map<pair<int, int>, int> cnt;
pair<int, int> edges[N];

void dfs(int u, bool crven, int k1, int k2) {
    if (nasao) return;
    crv[u] = crven;
    vis[u] = true;
    for (auto x : adj[u]) {
        if (u == k1 && x == k2) continue;
        if (x == k1 && u == k2) continue;
        if (vis[x] && crv[x] == crven) nasao = true;
        if (vis[x]) continue;
        dfs(x, crven^1, k1, k2);
    }
}

bool probaj(int i) {
    nasao = false;
    for (int j = 1; j <= n; j++) {
        if (vis[j]) continue;
        dfs(j, false, edges[i].first, edges[i].second);
    }
    if (cnt[edges[i]] > 1)
        nasao = true;
    return !nasao;
}

void case1() {
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= n; j++)
            vis[j] = false;
        ans += probaj(i);
    }
    cout << ans << "\n";
}

void case2() {
    int sz = n;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 1)
            q.push(i);

    while (!q.empty()) {
        auto u = q.front(); q.pop();
        sz--;
        cyc[u] = true;
        for (auto x : adj[u]) {
            if (--indeg[x] == 1)
                q.push(x);
        }
    }

    if (sz % 2 == 0) {
        int ans = m;
        for (int i = 0; i < m; i++) {
            auto [u, v] = edges[i];
            if (cnt[{u, v}] > 1) {
                ans--; continue;
            }
        }
        cout << ans << "\n";
    } else {
        int ans = m;
        for (int i = 0; i < m; i++) {
            auto [u, v] = edges[i];
            if (cnt[{u, v}] > 1) {
                ans--; continue;
            }
            if (cyc[u] && cyc[v])
                ans--;
        }

        cout << ans << "\n";
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        indeg[u]++;
        indeg[v]++;
        edges[i] = {u, v};
        cnt[{u, v}]++;
        cnt[{v, u}]++;

        if (u == v) {
            indeg[u]--;
            cnt[{u, v}]--;
        }
    }
    if (n <= 1000 && m <= 2000) {
        case1(); return;
    } else {
        case2(); return;
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t=1; //cin >> t;
    while (t--) {
        solve();
    }
}

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