Submission #522232

#TimeUsernameProblemLanguageResultExecution timeMemory
522232blueCijanobakterije (COCI21_cijanobakterije)C++17
70 / 70
78 ms12916 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <deque> using namespace std; using vi = vector<int>; using ll = long long; #define sz(x) int(x.size()) const int mx = 100'000; vi edge[1+mx]; int n, m; int res = 0; vi visit(1+mx, 0); vector< pair<int, int> > V; //dist, node void dfs(int u, int d) { // cerr << "dfs " << u << ' ' << d << '\n'; V.push_back({-d, u}); visit[u] = 1; for(int v: edge[u]) { if(visit[v]) continue; dfs(v, d+1); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int j = 1; j <= m; j++) { int a, b; cin >> a >> b; edge[a].push_back(b); edge[b].push_back(a); } for(int i = 1; i <= n; i++) { if(visit[i]) continue; // cerr << "component = " << i << '\n'; dfs(i, 0); sort(V.begin(), V.end()); for(auto y: V) visit[y.second] = 0; int src = V[0].second; V.clear(); // cerr << "cleared\n"; dfs(src, 0); sort(V.begin(), V.end()); res -= V[0].first - 1; V.clear(); } cout << res << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...