— Dark mode

Aalto Competitive Programming 2025 - wk6 - Wed

Fragile network

  • Start: 2025-10-08 16:20:00
  • End: 2025-10-08 17:50:00
Submission details
Task:Fragile network
Sender:aalto25f_003
Submission time:2025-10-08 16:59:27 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#2ACCEPTED0.01 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.07 sdetails
#7ACCEPTED0.06 sdetails
#80.07 sdetails
#90.06 sdetails
#100.06 sdetails
#110.01 sdetails
#120.01 sdetails
#130.01 sdetails
#140.03 sdetails
#150.01 sdetails
#160.01 sdetails
#170.01 sdetails
#180.01 sdetails
#190.01 sdetails
#200.01 sdetails
#210.01 sdetails

Code

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e5 + 5;

int n;
vector<int> g[N];
int d[N];
int nxt;
bool vis[N];
vector<pair<int, int> > ans;

void bfs(int src) {
  queue<int> q;
  q.push(src);
  memset(d, -1, sizeof(d));
  d[src] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
}

void dfs(int u) {
  bool f = true;
  vis[u] = true;
  for (int v : g[u]) {
    if (!vis[v]) {
      f = false;
      dfs(v);
    }
  }
  if (f) {
    ans.emplace_back(nxt, u);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int a, b;
    cin >> a >> b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  bfs(1);
  nxt = 1;
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    if (d[i] > mx) {
      mx = d[i];
      nxt = i;
    }
  }
  bfs(nxt);
  int lst = nxt;
  mx = 0;
  for (int i = 1; i <= n; i++) {
    if (d[i] > mx) {
      mx = d[i];
      lst = i;
    }
  }
  ans.emplace_back(nxt, lst);
  while (lst != nxt) {
    vis[lst] = true;
    for (int v : g[lst]) {
      if (d[v] == d[lst] - 1) {
        lst = v;
        break;
      }
    }
  }
  vis[nxt] = true;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i);
    }
  }
  cout << ans.size() << '\n';
  for (auto x : ans) {
    cout << x.first << ' ' << x.second << '\n';
  }
  return 0;
}

Test details

Test 1

Verdict:

input
10
1 5
1 7
1 8
1 3
...
view save

correct output
5
5 2
7 9
8 6
3 10
...
view save

user output
8
2 3
2 4
2 5
2 6
...
view save

Test 2

Verdict: ACCEPTED

input
10
4 5
3 4
2 3
9 10
...
view save

correct output
1
10 1
view save

user output
1
10 1
view save

Test 3

Verdict:

input
10
1 8
1 3
3 5
5 7
...
view save

correct output
3
7 10
8 2
1 9
view save

user output
4
9 2
9 7
9 8
9 10
view save

Test 4

Verdict:

input
10
1 5
3 7
2 10
3 8
...
view save

correct output
3
10 8
6 4
5 9
view save

user output
5
9 5
9 4
9 6
9 8
...
view save

Test 5

Verdict:

input
10
4 8
3 4
4 6
2 3
...
view save

correct output
3
8 7
10 9
1 6
view save

user output
4
6 10
6 7
6 8
6 9
view save

Test 6

Verdict:

input
100000
1 56967
1 56618
1 42321
1 82550
...
view save

correct output
50000
56967 16911
56618 39942
42321 99902
82550 2538
...
view save

user output
99998
2 3
2 4
2 5
2 6
...
view save

Test 7

Verdict: ACCEPTED

input
100000
92297 92298
23511 23512
68057 68058
65434 65435
...
view save

correct output
1
100000 1
view save

user output
1
100000 1
view save

Test 8

Verdict:

input
100000
17747 97512
10397 12053
679 6975
4013 14565
...
view save

correct output
25057
92881 76094
20353 87429
16069 96487
71186 52809
...
view save

user output
50112
65284 61386
65284 41434
65284 80509
65284 43334
...
view save

Test 9

Verdict:

input
100000
72941 72942
11232 11233
73464 73465
30042 30043
...
view save

correct output
489
16423 85168
20707 94190
36505 54940
96411 44067
...
view save

user output
976
95735 78973
95735 21977
95735 4831
95735 5346
...
view save

Test 10

Verdict:

input
100000
31451 31452
7473 7474
24056 24057
85181 85182
...
view save

correct output
51
25638 2983
87594 87371
92001 50610
46744 100000
...
view save

user output
100
69631 84893
69631 63319
69631 285
69631 140
...
view save

Test 11

Verdict:

input
10
1 2
1 3
3 4
3 5
...
view save

correct output
2
2 6
4 10
view save

user output
3
10 6
10 2
10 4
view save

Test 12

Verdict:

input
7
1 2
2 3
2 4
1 5
...
view save

correct output
2
4 7
3 6
view save

user output
3
3 6
3 4
3 7
view save

Test 13

Verdict:

input
6
1 2
1 3
1 4
4 5
...
view save

correct output
2
3 6
2 5
view save

user output
3
5 2
5 3
5 6
view save

Test 14

Verdict:

input
65538
1 2
1 3
1 4
3 5
...
view save

correct output
16385
34 36
40 42
35 41
48 50
...
view save

user output
32769
33 32799
33 2
33 4
33 16415
...
view save

Test 15

Verdict:

input
11
1 2
1 3
2 4
2 5
...
view save

correct output
2
9 11
8 10
view save

user output
3
8 10
8 9
8 11
view save

Test 16

Verdict:

input
7
1 2
1 3
2 4
2 5
...
view save

correct output
2
5 7
4 6
view save

user output
3
4 6
4 5
4 7
view save

Test 17

Verdict:

input
7
1 2
1 3
2 4
2 5
...
view save

correct output
2
5 7
4 6
view save

user output
3
4 6
4 5
4 7
view save

Test 18

Verdict:

input
10
8 4
3 4
4 6
2 3
...
view save

correct output
3
8 7
10 9
1 6
view save

user output
4
6 10
6 7
6 8
6 9
view save

Test 19

Verdict:

input
7
1 2
1 5
2 3
2 6
...
view save

correct output
2
6 7
3 4
view save

user output
3
3 4
3 6
3 7
view save

Test 20

Verdict:

input
8
1 2
1 3
2 4
2 5
...
view save

correct output
3
4 7
6 8
1 5
view save

user output
4
4 8
4 5
4 6
4 7
view save

Test 21

Verdict:

input
10
2 1
3 1
4 2
5 4
...
view save

correct output
3
9 8
6 10
3 7
view save

user output
5
6 3
6 7
6 8
6 9
...
view save

Tasks

A FenceB Microservice hellC Online feudD LaddersE Fragile network

Submissions (aalto25f_003)

2025-10-08 17:11:58 2025-10-08 17:09:51 2025-10-08 17:06:06 2025-10-08 17:05:51 2025-10-08 16:59:27