# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497198 | 2021-12-22T16:59:52 Z | CyberCow | Shymbulak (IZhO14_shymbulak) | C++17 | 1500 ms | 8756 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <string> #include <cmath> #include <map> #include <unordered_map> #include <unordered_set> #include <fstream> #include <iomanip> #include <iterator> #include <stack> #include <deque> using namespace std; using ll = long long; vector<int> v[200004]; queue<int> q; int color[200004], ans = 0, n, ma, c[200004]; void solve() { int i, j, x, y, oo = 1000000000; cin >> n; for ( i = 0; i < n; i++) { cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } color[1] = 1; q.push(1); while (!q.empty()) { x = q.front(); q.pop(); for ( i = 0; i < v[x].size(); i++) { if (!color[v[x][i]]) { color[v[x][i]] = color[x] + 1; q.push(v[x][i]); } } } int ind = 0; for ( i = 1; i <= n; i++) { if (color[i] > ma) { ma = color[i]; ind = i; } color[i] = 0; } color[ind] = 1; q.push(ind); while (!q.empty()) { x = q.front(); q.pop(); for (i = 0; i < v[x].size(); i++) { if (!color[v[x][i]]) { color[v[x][i]] = color[x] + 1; q.push(v[x][i]); } } } ma = 0; for (i = 1; i <= n; i++) { ma = max(ma, color[i]); color[i] = 0; } for ( j = 1; j <= n; j++) { c[j] = 1; color[j] = 1; q.push(j); while (!q.empty()) { x = q.front(); q.pop(); for (i = 0; i < v[x].size(); i++) { if (c[v[x][i]] == 0 || c[v[x][i]] == c[x] + 1) { color[v[x][i]] += color[x]; } if (!c[v[x][i]]) { c[v[x][i]] = c[x] + 1; q.push(v[x][i]); } } } for ( i = 1; i <= n; i++) { if (c[i] == ma) { ans += color[i]; } c[i] = 0; color[i] = 0; } } cout << ans/2; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solve(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 2 ms | 4940 KB | Output is correct |
3 | Correct | 2 ms | 4940 KB | Output is correct |
4 | Correct | 2 ms | 4940 KB | Output is correct |
5 | Correct | 2 ms | 4940 KB | Output is correct |
6 | Correct | 2 ms | 4940 KB | Output is correct |
7 | Correct | 2 ms | 4940 KB | Output is correct |
8 | Correct | 2 ms | 4940 KB | Output is correct |
9 | Correct | 2 ms | 4940 KB | Output is correct |
10 | Correct | 2 ms | 4940 KB | Output is correct |
11 | Correct | 2 ms | 4940 KB | Output is correct |
12 | Correct | 2 ms | 4940 KB | Output is correct |
13 | Correct | 3 ms | 4940 KB | Output is correct |
14 | Correct | 8 ms | 4940 KB | Output is correct |
15 | Incorrect | 8 ms | 4940 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 5052 KB | Output is correct |
2 | Correct | 13 ms | 4940 KB | Output is correct |
3 | Incorrect | 24 ms | 4940 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1561 ms | 8756 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |