Submission #1268730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268730		s1zzl3	Cijanobakterije (COCI21_cijanobakterije)	C++20	36 / 70	1093 ms	9284 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
typedef long long ll;
const int MAXN = 1e5+5;

int n,m;
vector<int> graph[MAXN];
bool visited[MAXN];
int dist[MAXN];

// DFS để đánh dấu thành phần liên thông
void dfsMark(int u) {
    visited[u] = true;
    for (int v : graph[u]) {
        if(!visited[v]) dfsMark(v);
    }
}

// DFS để tính khoảng cách xa nhất từ 1 node
void dfsDist(int u, int pre) {
    for (int v : graph[u]) {
        if(v != pre) {
            dist[v] = dist[u] + 1;
            dfsDist(v,u);
        }
    }
}

// Tính đường kính của 1 thành phần liên thông chứa node "start"
int calcDiameter(int start) {
    // Lần 1: tìm đỉnh xa nhất từ start
    fill(dist, dist+n+1, -1);
    dist[start] = 0;
    dfsDist(start,-1);

    int far = start;
    for (int i=1; i<=n; i++) {
        if(dist[i] > dist[far]) far = i;
    }

    // Lần 2: từ far tìm xa nhất
    fill(dist, dist+n+1, -1);
    dist[far] = 0;
    dfsDist(far,-1);

    int diam = 0;
    for (int i=1; i<=n; i++) {
        if(dist[i] >= 0) diam = max(diam, dist[i]);
    }
    return diam+1; // +1 để tính số đỉnh (nếu muốn tính theo số cạnh thì bỏ +1)
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int u,v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    ll res = 0;
    fill(visited, visited+n+1, false);

    for (int i=1; i<=n; i++) {
        if(!visited[i]) {
            // đánh dấu cả thành phần
            dfsMark(i);
            // tính đường kính của thành phần này
            res += calcDiameter(i);
        }
    }

    cout << res << nl;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 6
• Subtask 3: 6 / 6
• Subtask 4: 15 / 15
• Subtask 5: 0 / 28