Saturday, June 15, 2024

# Codeforces Round #436 (Div. 2), problem: (F) Cities Excursions Solution In C/C++

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3005, INF = 0x3f3f3f3f;

int n, m, q, f[N][12];
bool vis[N];

struct Edge {
int to;
Edge *next;
Edge () {}
Edge (int to, Edge *next) : to(to), next(next) {}
}*head[N], pool[N << 1], *pis = pool;

void Min (int &x, int y) { if (x > y) x = y; }

int fr[N], tt[N], ins[N];

void Dfs (int x) {
vis[x] = 1;
for (Edge *now = head[x]; now; now = now -> next) {
Min(fr[now -> to], x);
if (!vis[now -> to]) Dfs(now -> to);
}
}

void Dfs2 (int x) {
if (tt[x] != INF) return ;
if (fr[x] == INF || ins[fr[x]]) { tt[x] = -1; return ; }
ins[x] = 1;
Dfs2(fr[x]);
tt[x] = tt[fr[x]] == -1 ? -1 : tt[fr[x]] + 1;
ins[x] = 0;
}

struct E { int x, y, k, id; bool operator < (const E &rhs) const { return y < rhs.y; } }e[400005];

int i, ans[400005];

int main () {
scanf(“%d%d%d”, &n, &m, &q);
for (int i = 1, x, y; i <= m; ++i) {
scanf(“%d%d”, &x, &y);
}
for (int i = 0; i < q; ++i) scanf(“%d%d%d”, &e[i].x, &e[i].y, &e[i].k), e[i].id = i;
sort(e, e + q);
for (int x, y, k, lay = -1, ans, w = q; w–; ) {
x = e[w].x; y = e[w].y; k = e[w].k;
if (lay != y) {
memset(vis, 0, sizeof vis), memset(fr, 0x3f, sizeof fr), memset(tt, 0x3f, sizeof tt), Dfs(y), tt[y] = 1;
for (i = 1; i <= n; ++i) Dfs2(i), f[i][0] = fr[i];
for (int j = 1; j < 12; ++j) for (i = 1; i <= n; ++i) if (f[i][j – 1] != INF) f[i][j] = f[f[i][j – 1]][j – 1];
}
if (fr[x] == 0x3f3f3f3f) ::ans[e[w].id] = -1;
else {
if (tt[x] == -1 || tt[x] < k) ::ans[e[w].id] = -1;
else {
–k;
for (int j = 0; j < 12; ++j) if (k >> j & 1) x = f[x][j];
::ans[e[w].id] = x;
}
// for (i = 1; i < k && x != y; ++i) x = fr[x]; if (i != k) { ::ans[e[j].id] = -1; continue ; } ans = x;
// for (; i <= 3000 && x != y; ++i) x = fr[x];
// ::ans[e[j].id] = x != y ? -1 : ans;
}
lay = y;
}
for (int i = 0; i < q; ++i) printf(“%d\n”, ans[i]);
return 0;
}

## Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

## The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

## Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

## Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

Coachella Valley Music and Arts Festival, one of the...

## 2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

### Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

### The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

### Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

### Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

### Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

### 2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

### Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

### Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

### Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...