#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=1e5;
int n, m;
vector<int> adj[mxN];
bool vis[mxN];
ar<int, 2> dfs(int u) {
vis[u]=1;
ar<int, 2> d={};
int diam=0;
for (int v : adj[u])
if (!vis[v]) {
ar<int, 2> x=dfs(v);
diam=max(diam, x[0]);
if (x[1]+1>d[0]) {
swap(d[0], d[1]);
d[0]=x[1]+1;
} else if (x[1]+1>d[1])
d[1]=x[1]+1;
}
diam=max(diam, d[0]+d[1]);
return {diam, d[0]};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i=0; i<m; ++i) {
int u, v;
cin >> u >> v, --u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int ans=0;
for (int i=0; i<n; ++i)
if (!vis[i])
ans+=dfs(i)[0]+1;
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3284 KB |
Output is correct |
2 |
Correct |
11 ms |
4036 KB |
Output is correct |
3 |
Correct |
17 ms |
4836 KB |
Output is correct |
4 |
Correct |
20 ms |
5580 KB |
Output is correct |
5 |
Correct |
27 ms |
6328 KB |
Output is correct |
6 |
Correct |
35 ms |
7112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
13232 KB |
Output is correct |
2 |
Correct |
3 ms |
3148 KB |
Output is correct |
3 |
Correct |
5 ms |
3676 KB |
Output is correct |
4 |
Correct |
7 ms |
4172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2764 KB |
Output is correct |
3 |
Correct |
2 ms |
2656 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
4 ms |
3276 KB |
Output is correct |
6 |
Correct |
11 ms |
3916 KB |
Output is correct |
7 |
Correct |
9 ms |
4460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2668 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
1 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2668 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2672 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
3 ms |
2676 KB |
Output is correct |
11 |
Correct |
2 ms |
2672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3284 KB |
Output is correct |
2 |
Correct |
11 ms |
4036 KB |
Output is correct |
3 |
Correct |
17 ms |
4836 KB |
Output is correct |
4 |
Correct |
20 ms |
5580 KB |
Output is correct |
5 |
Correct |
27 ms |
6328 KB |
Output is correct |
6 |
Correct |
35 ms |
7112 KB |
Output is correct |
7 |
Correct |
27 ms |
13232 KB |
Output is correct |
8 |
Correct |
3 ms |
3148 KB |
Output is correct |
9 |
Correct |
5 ms |
3676 KB |
Output is correct |
10 |
Correct |
7 ms |
4172 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2764 KB |
Output is correct |
13 |
Correct |
2 ms |
2656 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
4 ms |
3276 KB |
Output is correct |
16 |
Correct |
11 ms |
3916 KB |
Output is correct |
17 |
Correct |
9 ms |
4460 KB |
Output is correct |
18 |
Correct |
3 ms |
2668 KB |
Output is correct |
19 |
Correct |
1 ms |
2636 KB |
Output is correct |
20 |
Correct |
2 ms |
2636 KB |
Output is correct |
21 |
Correct |
2 ms |
2672 KB |
Output is correct |
22 |
Correct |
1 ms |
2636 KB |
Output is correct |
23 |
Correct |
2 ms |
2668 KB |
Output is correct |
24 |
Correct |
2 ms |
2636 KB |
Output is correct |
25 |
Correct |
2 ms |
2672 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
3 ms |
2676 KB |
Output is correct |
28 |
Correct |
2 ms |
2672 KB |
Output is correct |
29 |
Correct |
37 ms |
7024 KB |
Output is correct |
30 |
Correct |
8 ms |
3828 KB |
Output is correct |
31 |
Correct |
23 ms |
6520 KB |
Output is correct |
32 |
Correct |
15 ms |
4560 KB |
Output is correct |
33 |
Correct |
30 ms |
6900 KB |
Output is correct |
34 |
Correct |
25 ms |
5304 KB |
Output is correct |
35 |
Correct |
23 ms |
6732 KB |
Output is correct |
36 |
Correct |
24 ms |
5836 KB |
Output is correct |
37 |
Correct |
29 ms |
6896 KB |
Output is correct |
38 |
Correct |
33 ms |
6328 KB |
Output is correct |
39 |
Correct |
37 ms |
6724 KB |
Output is correct |