| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 623006 |
2022-08-05T01:51:04 Z |
MinaRagy06 |
Network (BOI15_net) |
C++17 |
|
1 ms |
356 KB |
#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl '\n'
#define int long long
vector<int> adj[2006];
int dist[2006][2006];
void dfs(int i, int sum, int src, int par)
{
dist[src][i] = sum;
for (auto nxt : adj[i]) if (nxt != par) dfs(nxt, sum+1, src, i);
}
signed main()
{
lesgooo;
int n, u, v;
cin >> n;
mt19937 rng(2005);
for (int i = 1; i < n; i++) cin >> u >> v, adj[--u].push_back(--v), adj[v].push_back(u);
set<int> leaf;
for (int i = 0;i < n; i++)
{
dfs(i, 0, i, -1);
if (adj[i].size() == 1) leaf.insert(i);
}
cout << (leaf.size()+1)/2 << endl;
int temp = *leaf.begin();
while (leaf.size() > 1)
{
int cur = *leaf.begin(), mx = -1;
vector<int> aa;
for (int i = 0; i < n; i++) if (i != cur && leaf.find(i) != leaf.end())
{
if (dist[cur][i] > mx) mx = dist[cur][i], aa.clear(), aa.push_back(i);
else if (dist[cur][i] == mx) aa.push_back(i);
}
int x= aa[rng()%aa.size()];
cout << cur+1 << " " << x+1 << endl;
leaf.erase(leaf.begin()), leaf.erase(x);
}
if (leaf.size()) cout << *leaf.begin()+1 << " " << (*leaf.begin()+1)%n+1 << endl, leaf.erase(leaf.begin());
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:28:9: warning: unused variable 'temp' [-Wunused-variable]
28 | int temp = *leaf.begin();
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
284 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
356 KB |
Breaking single line is causing network to disconnect. |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
284 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
356 KB |
Breaking single line is causing network to disconnect. |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
284 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
356 KB |
Breaking single line is causing network to disconnect. |
| 13 |
Halted |
0 ms |
0 KB |
- |
