Editorial for VOI 15 Bài 3 - Kế hoạch cải tổ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>

const int N = 100005;

using namespace std;

vector<II> e;
VI a[N];
int low[N], num[N], cnt[N], par[N], sz[N];
bool isBridge[N];
int n, m, timer, cntBridge, cc;

void dfs(int u) {
    num[u] = ++timer; low[u] = INT_MAX; cnt[cc]++; sz[u] = 1;
    TR(v, a[u]) if (*v != par[u]) {
        if (num[*v]) low[u] = min(low[u], num[*v]);
        else {
            par[*v] = u;
            dfs(*v);
            low[u] = min(low[u], low[*v]);
            sz[u] += sz[*v];
        }
    }
    if (low[u] >= num[u] && par[u])
        cntBridge += isBridge[u] = 1;
}

LL solve() {
    if (cc > 2) return 0;
    if (cc == 2) return (LL)cnt[1] * cnt[2] * (m - cntBridge);
    LL ans = 0, maxE = (LL)n * (n - 1) / 2;
    TR(it, e) {
        int u = it -> X;
        int v = it -> Y;
        if (num[u] > num[v]) swap(u, v);
        if (par[v] == u && isBridge[v])
            ans += (LL)sz[v] * (sz[1] - sz[v]) - 1;
        else
            ans += maxE - m;
    }
    return ans;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
        e.PB(MP(u, v));
    }
    REP(i, 1, n) if (num[i] == 0) {
        cc++;
        dfs(i);
    }
    cout << solve();
    return 0;
}

Comments

Please read the guidelines before commenting.



  • 0
    tuan10a3  commented on Feb. 12, 2025, 12:59 p.m.

    include <bits/stdc++.h>

    define th1 first

    define th2 second

    define int long long

    define _(k) ((k) & (-(k)))

    using namespace std;

    const int N = 5 + 2e5; const int INF = 0x3f3f3f3f; int n, m, num[N], low[N], vis[N], hint[N], pa[N], cnt = 0, cau = 0, khop = 0, sz[N], kq = 0; int amount = 0, node = 0; vector<int> g[N];

    struct T { int u, v; } e[N];

    void dfs(int u) { num[u] = low[u] = ++cnt; sz[u] = 1; for (int id : g[u]) { if (vis[id]) continue; vis[id] = 1; int v = e[id].u + e[id].v - u; if (!num[v]) { pa[v] = u; dfs(v); sz[u] += sz[v]; low[u] = min(low[u], low[v]); if (low[v] > num[u]) { cau++; kq += (sz[v] * (n - sz[v]) - 1); } } else low[u] = min(low[u], num[v]); } }

    void solve() { if (amount >= 3) cout << 0 << '\n'; else if (amount == 2) { cout << (m - cau) * node * (n - node) << '\n'; } else { kq += ((m - cau) * (n * (n - 1) / 2 - m)); cout << kq; } }

    int32t main() { iosbase::syncwithstdio(0); cin.tie(0); #define TASKNAME "a" if (fopen(TASKNAME".inp", "r")) { freopen(TASKNAME".inp", "r", stdin); freopen(TASKNAME".out", "w", stdout); } cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> e[i].u >> e[i].v; g[e[i].u].pushback(i); g[e[i].v].pushback(i); }

    amount = 0;
    for (int i = 1; i <= n; i++)
        if (!num[i]) {
            amount++;
            dfs(i);
            if (node == 0) node = cnt;
        }
    
    solve();
    return 0;
    

    }