Teads Sponsored Contest (successes: 3/10)


#1
#include <algorithm>
#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main() {
int N; // the number of adjacency relations
cin >> N;
map<int, map<int, int>> adj;  // map<xi, map<yi, distance>>
for (int i = 0; i < N; i++) {
    int xi, // the ID of a person which is adjacent to yi
        yi; // the ID of a person which is adjacent to xi
    cin >> xi >> yi;
    // adj[xi][xi] = adj[yi][yi] = 0;
    adj[xi][yi] = adj[yi][xi] = 1;
    for (auto x : adj[xi])
        if (yi != x.first && (!adj[yi][x.first] || adj[yi][x.first] > x.second + 1))
            adj[yi][x.first] = adj[x.first][yi] = x.second + 1;
    for (auto y : adj[yi])
        if (xi != y.first && (!adj[xi][y.first] || adj[xi][y.first] > y.second + 1))
            adj[xi][y.first] = adj[y.first][xi] = y.second + 1;
}
/*// Debug
for (const auto& x : adj) {
    cerr << "From " << x.first << ":\n";
    for (const auto& y: x.second)
        cerr << "\tto " << y.first << ": " << y.second << "\n";
}*/
int res {-1};
for (const auto& x : adj) {
    const int required_steps {max_element(x.second.cbegin(), x.second.cend(), [] (pair<int, int> a, pair<int, int> b) {return a.second < b.second;})->second};
    if (res > required_steps || res == -1)
        res = required_steps;
}
cout << res << endl;
return 0;
}

Sorry for using nested maps with graphs, I know it’s gross.
Basically, each time I get a new input I update the graph to turn it into a complete graph; finally, I look for the minimum maximum edge weight.

  • The first three testcases work just fine.
  • Testcases 4-7 and 10 output wrong results.
  • Also, testcases 8-9 cause a timeout, but I’d like to debug first.

Thanks for your time!