Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### KP56's blog

By KP56, history, 2 months ago,

Today I've started solving problems on the AtCoder website. For the past 30 minutes I've been trying to solve the "Change Usernames" problem (https://atcoder.jp/contests/abc285/tasks/abc285_d). It seems to be quite simple, but for some reason my solution gets a wrong answer verdict. After trying different approaches (firstly with unordered sets then with cycle detection), I checked the editorial only to notice that the suggested solution is actually the cycle detection one. One thing I noticed is that each of my approaches failed on the same test cases. It seems like I keep doing the same mistake. Can anyone see an issue?

Here is the code:

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define pf push_front
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define endl "\n"
#define in(x) cin >> x
#define inll(x) ll x; in(x)
#define ini(x) int x; in(x)
#define instr(x) string x; in(x)

//https://codeforces.com/blog/entry/62393
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}

size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};

bool isThereACycle(int at, vector<int> &adj_list, vector<bool> &vis) {
vis[at] = true;

if (adj_list[at] == -1) {
return true;
} else {
if (vis[adj_list[at]]) {
return false;
}

return isThereACycle(adj_list[at], adj_list, vis);
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);

ini(n);
vector<pair<string,string>> strings;
for (int i = 0; i < n; i++) {
instr(a);
instr(b);
strings.pb(mp(a,b));
}

vector<int> adj_list(strings.size(), -1);
unordered_map<string,int> keys;
for (int i = 0; i < strings.size(); i++) {
auto j = strings[i];

keys[j.first] = i;
}

for (int i = 0; i < strings.size(); i++) {
auto j = strings[i];
if (keys.find(j.second) != keys.end()) {
adj_list[i] = keys[j.second];
}
}

vector<bool> vis(strings.size());
for (int i = 0; i < n; i++) {
if (!vis[i]) {
if (isThereACycle(i, adj_list, vis)) {
cout << "Yes" << endl;
return 0;
}
}
}

cout << "No" << endl;
}


• -21

 » 2 months ago, # |   -8 Auto comment: topic has been updated by KP56 (previous revision, new revision, compare).
 » 2 months ago, # |   +21 Simply looking at the title, I was like, you can change your atcoder username?
 » 2 months ago, # |   0 a node u might be adjacent to many other nodes, not one
•  » » 2 months ago, # ^ |   0 Not in this case. If you read the problem you can see that S and T are distinct.
 » 2 months ago, # |   -8 Managed to solve the issue. The problem was with this piece of code: if (vis[adj_list[at]]) { return false; }I assumed that if we visit a node which has been visited, it means that there is a cycle. That may not be the case however, because if we first run DFS on a node of a non cycle and then on a node connected to that node, then we will also try to visit a visited node.