Counting Rooms
Thinking
used simple bfs in a grid
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
bool inrange(ll x, ll y, ll n, ll m)
{
if (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)))
return true;
return false;
}
int main()
{
ll n, m;
cin >> n >> m;
vector<string> v(n);
vector<vector<ll>> vis(n, vector<ll>(m));
for (auto &i : v)
{
cin >> i;
}
ll cnt = 0;
queue<pair<ll, ll>> q;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == '#')
continue;
if (vis[i][j] == 1)
continue;
q.push({i, j});
vis[i][j] = 1;
cnt++;
while (q.size() > 0)
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if ((inrange(nx, ny, n, m) && v[nx][ny] != '#') && vis[nx][ny] == 0)
{
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
}
cout << cnt;
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Building Roads
Thinking
do bfs and store the starting vertex of each bfs traversal
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> v(n);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
x--;
y--;
v[x].push_back(y);
v[y].push_back(x);
}
vector<ll> vis(n, 0);
vector<ll> heads;
for (ll i = 0; i < n; i++)
{
if (vis[i] == 1)
continue;
heads.push_back(i);
queue<ll> q;
q.push(i);
vis[i] = 1;
while (q.size())
{
ll curr = q.front();
q.pop();
for (auto child : v[curr])
{
if (vis[child] == 1)
continue;
vis[child] = 1;
q.push(child);
}
}
}
// for(auto i: heads)
// {
// cout<<i<<" ";
// }
cout << heads.size() - 1 << "\n";
for (ll i = 0; i < ((ll)(heads.size() - 1)); i++)
{
cout << heads[i] + 1 << " " << heads[i + 1] + 1 << "\n";
}
}
}
Message Route
Thinking
do bfs and store parent
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> v(n);
while (m--)
{
ll x, y;
cin >> x >> y;
x--;
y--;
v[x].push_back(y);
v[y].push_back(x);
}
vector<ll> vis(n, 0);
queue<ll> q;
q.push(0);
vis[0] = 1;
vector<ll> prev(n, -1);
while (q.size())
{
ll curr = q.front();
q.pop();
for (auto child : v[curr])
{
if (vis[child] == 1)
continue;
q.push(child);
vis[child] = 1;
prev[child] = curr;
}
}
if (vis[n - 1] == 0)
{
cout << "IMPOSSIBLE\n";
continue;
}
vector<ll> res;
ll cur = n - 1;
// res.push_back();
while (cur != 0)
{
res.push_back(cur);
cur = prev[cur];
}
res.push_back(cur);
reverse(res.begin(), res.end());
cout << res.size() << "\n";
for (auto i : res)
cout << i + 1 << " ";
}
}
Building Teams
Thinking
check if the graph can be divided into a bipartite graph using bfs.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<vector<ll>> adj(100001);
vector<ll> vis(100001, 0);
vector<ll> team(100001, 0);
bool dfs(ll node, ll ct)
{
vis[node] = 1;
team[node] = ct;
for (auto &i : adj[node])
{
if (team[i] == 0)
{
bool temp = dfs(i, 3 - ct);
if (temp == false)
return false;
}
else if (team[i] == ct)
{
return false;
}
}
return true;
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
while (m--)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
bool ans = true;
for (ll i = 1; i <= n; i++)
{
if (vis[i])
continue;
ll res = dfs(i, 1);
if (!res)
{
ans = false;
break;
}
}
if (ans)
{
for (ll i = 1; i <= n; i++)
cout << team[i] << " ";
}
else
cout << "IMPOSSIBLE\n";
}
}
Round Trip
Thinking
use graph coloring to detect and print cycle by storing parent for each node.. as soon as cycle is detected ,.. print cycle and end program
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll paret[100005];
ll colour[100005];
ll vis[100005];
vector<vector<ll>> adj(100005);
bool dfs(int node, int parent)
{
vis[node] = 1;
paret[node] = parent;
colour[node] = 1;
for (auto child : adj[node])
{
if (child != parent && colour[child] == 1)
{
vector<ll> res;
ll x = node;
while (x != child)
{
res.push_back(x);
x = paret[x];
}
res.push_back(x);
// if(res[0]==res[res.size()-1])
// res.pop_back();
res.push_back(res[0]);
cout << res.size() << "\n";
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
else if (child != parent && colour[child] == 0)
{
bool temp = dfs(child, node);
if (temp == true)
{
vector<ll> res;
ll x = paret[child];
while (paret[x] != child)
{
res.push_back(x);
x = paret[x];
}
cout << res.size() << "\n";
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
}
}
colour[node] = 2;
return false;
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
while (m--)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 1)
{
continue;
}
// memset(colour,0,sizeof colour);
dfs(i, 0);
}
cout << "IMPOSSIBLE\n";
}
Monsters
Thinking
places where the monsters can reach before the person, can be considered to be as good as blocked,so first run a multisource bfs with all the monsters to find the time taken to reach all non blocked cells by the monsters then run a bfs using the persons position to find the time taken by the person to reach there finally if there is any boundary cell such that the person can reach it before the monsters,.. then print the path to it otherwise print impossible
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
bool issafe(ll x, ll y, ll n, ll m)
{
return ((0 <= x) && (x < n)) && ((0 <= y) && (y < m));
}
char pro(pair<ll, ll> a, pair<ll, ll> b)
{
if ((a.second + 1) == (b.second))
{
return 'R';
}
else if ((a.second - 1) == (b.second))
{
return 'L';
}
else if ((a.first - 1) == (b.first))
{
return 'U';
}
else
return 'D';
}
int main()
{
fastio;
ll t = 1;
// cin >> t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
queue<pair<ll, ll>> q;
vector<vector<ll>> dist(n, vector<ll>(m, LLONG_MAX));
vector<vector<bool>> vis(n, vector<bool>(m, false));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'M')
{
q.push({i, j});
dist[i][j] = 0;
vis[i][j] = true;
}
}
}
while (q.size() > 0)
{
auto z = q.front();
ll x = z.first;
ll y = z.second;
q.pop();
for (ll i = 0; i < 4; i++)
{
ll nx = x + dx[i];
ll ny = y + dy[i];
if ((issafe(nx, ny, n, m) && (v[nx][ny] != '#')) && (!vis[nx][ny]))
{
dist[nx][ny] = dist[x][y] + 1;
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
vector<vector<ll>> dista(n, vector<ll>(m, LLONG_MAX));
vector<vector<bool>> vista(n, vector<bool>(m, false));
queue<pair<ll, ll>> qa;
map<pair<ll, ll>, pair<ll, ll>> par;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
qa.push({i, j});
dista[i][j] = 0;
vista[i][j] = true;
par[{i, j}] = {i, j};
}
}
}
while (qa.size() > 0)
{
auto z = qa.front();
ll x = z.first;
ll y = z.second;
qa.pop();
for (ll i = 0; i < 4; i++)
{
ll nx = x + dx[i];
ll ny = y + dy[i];
if (((issafe(nx, ny, n, m) && v[nx][ny] != '#')) && (!vista[nx][ny]))
{
dista[nx][ny] = dista[x][y] + 1;
vista[nx][ny] = true;
qa.push({nx, ny});
par[{nx, ny}] = {x, y};
}
}
}
vector<pair<ll, ll>> res;
bool f = true;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (((i == 0) || (j == 0)) || ((i == n - 1) || (j == m - 1)))
{
if (dista[i][j] < dist[i][j])
{
pair<ll, ll> z = {i, j};
while (par[z] != z)
{
res.push_back(z);
z = par[z];
}
res.push_back(z);
f = false;
break;
}
}
}
if (!f)
{
break;
}
}
// for (auto &i : res)
// {
// cout << i.first << " " << i.second << "\n";
// }
if (!f)
{
cout << "YES\n";
ll x = res.size();
cout << x - 1 << "\n";
reverse(res.begin(), res.end());
for (ll i = 0; i < x - 1; i++)
{
char ch = pro(res[i], res[i + 1]);
cout << ch;
}
}
else
{
cout << "NO\n";
}
// for (auto &i : dist)
// {
// for (auto &j : i)
// {
// cout << j << " ";
// }
// cout << "\n";
// }
}
}
Shortest Routes I
Thinking
simple djikstra
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin/>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
vector<ll> dist(n + 1, LLONG_MAX);
dist[1] = 0;
while (m--)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, 1});
while (pq.size())
{
ll distance = pq.top().first;
ll node = pq.top().second;
pq.pop();
if (distance > dist[node])
continue;
for (auto &child : adj[node])
{
if (dist[child.first] > distance + (child.second))
{
dist[child.first] = distance + (child.second);
pq.push({distance + (child.second), child.first});
}
}
}
for (ll i = 1; i <= n; i++)
cout << dist[i] << " ";
}
}
Shortest Routes II
Thinking
simple Floyd Warshall
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin/>>t;
while (t--)
{
ll n, m, q;
cin >> n >> m >> q;
vector<vector<pair<ll, ll>>> adj(n + 1);
// vector<ll> dist(n+1,LLONG_MAX);
// dist[1] = 0;
vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, LLONG_MAX));
while (m--)
{
ll u, v, w;
cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
for (ll i = 1; i <= n; i++)
dist[i][i] = 0;
for (ll k = 1; k <= n; k++)
{
for (ll i = 1; i <= n; i++)
{
for (ll j = 1; j <= n; j++)
{
if ((dist[i][k] != LLONG_MAX) && (dist[k][j] != LLONG_MAX))
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
while (q--)
{
ll x, y;
cin >> x >> y;
cout << ((dist[x][y] == LLONG_MAX) ? -1 : dist[x][y]) << "\n";
}
// for(ll i=1;i<=n;i++)
// cout<<dist[i]<<" ";
}
}
High Score
Thinking
negate the edge weights and use bellman ford to get the minimum negative score ,.. i.e. the max score in positive numbers
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<ll> vis(2501, 0);
void dfs(ll node, ll parent, vector<ll> &reachable, vector<vector<ll>> &adjrev)
{
if (vis[node] == 1)
{
return;
}
else
{
reachable.push_back(node);
vis[node] = 1;
for (auto &i : adjrev[node])
{
if (i == parent)
continue;
dfs(i, node, reachable, adjrev);
}
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
vector<pair<pair<ll, ll>, ll>> edges;
for (ll i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
edges.push_back({{u, v}, -w});
adj[u].push_back({v, -w});
}
vector<ll> dist(n + 1, LLONG_MAX);
dist[1] = 0;
for (ll i = 1; i <= n; i++)
{
for (ll j = 0; j < m; j++)
{
ll u = edges[j].first.first;
ll v = edges[j].first.second;
ll w = edges[j].second;
if (dist[u] != LLONG_MAX)
{
dist[v] = min(dist[v], dist[u] + w);
}
}
}
// bool f = true;
ll x = dist[n];
set<ll> temp;
for (ll j = 0; j < m; j++)
{
ll u = edges[j].first.first;
ll v = edges[j].first.second;
ll w = edges[j].second;
if (dist[u] != LLONG_MAX)
{
ll x = dist[v];
dist[v] = min(dist[v], dist[u] + w);
if (x != dist[v])
temp.insert(v);
}
}
for (auto &i : edges)
{
swap(i.first.first, i.first.second);
}
vector<vector<ll>> adjrev(n + 1);
for (ll i = 0; i < m; i++)
{
ll u = edges[i].first.first;
ll v = edges[i].first.second;
adjrev[u].push_back(v);
}
vector<ll> reachable;
dfs(n, -1, reachable, adjrev);
bool f = true;
for (auto &i : reachable)
{
if (temp.find(i) != temp.end())
{
f = false;
break;
}
}
// if (x != dist[n])
// {
// f = false;
// }
if (f)
cout << -dist[n] << "\n";
else
cout << "-1\n";
}
Flight Discount
Thinking
use state djikstra What is state djikstra you might ask:
State djikstra
This is an extension of djikstra algorithm in which you process each node as a state,.. i.e. you maintain a variable to denote whether the discount has been used till now or not,.. and you push it into the priority queue along with the node number,.. For further clarification,.. see the code.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
// adj[v].push_back({u, w});
}
priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;
vector<vector<ll>> dis(n + 1, vector<ll>(2, LLONG_MAX));
dis[1][0] = 0;
dis[1][1] = 0;
pq.push({0, 1, 1});
while (pq.size() > 0)
{
auto z = pq.top();
pq.pop();
ll dist = z[0];
ll node = z[1];
ll available = z[2];
if (dis[node][available] < dist)
continue;
for (auto &ch : adj[node])
{
if (available == 1)
{
if (dis[ch.first][1] > (dist + ch.second))
{
dis[ch.first][1] = dist + ch.second;
pq.push({dis[ch.first][1], ch.first, 1});
}
if (dis[ch.first][0] > (dist + (ch.second) / 2))
{
dis[ch.first][0] = (dist + (ch.second) / 2);
pq.push({dis[ch.first][0], ch.first, 0});
}
}
else
{
if (dis[ch.first][0] > (dist + (ch.second)))
{
dis[ch.first][0] = (dist + (ch.second));
pq.push({dis[ch.first][0], ch.first, 0});
}
}
}
}
cout << min(dis[n][0], dis[n][1]) << "\n";
}
Cycle Finding
Thinking
use bellman ford to detect the presence of a negative cycle,.. Now, to print it,.. run bellman ford again(keep track of parent of nodes),... now,.. take any node whose value gets updated and keep on visiting its parent until the node itself is found,.. and u have found ur cycle .
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
vector<vector<ll>> edges;
for (ll i = 0; i < m; i++)
{
ll x, y, w;
cin >> x >> y >> w;
adj[x].push_back({y, w});
edges.push_back({x, y, w});
}
vector<ll> dist(n + 1, 0);
dist[1] = 0;
for (ll i = 0; i < n; i++)
{
for (auto &edge : edges)
{
ll u = edge[0];
ll v = edge[1];
ll w = edge[2];
if (dist[u] != LLONG_MAX)
{
dist[v] = min(dist[v], dist[u] + w);
}
}
}
bool f = true;
vector<ll> par(n + 1, -1);
for (ll i = 0; i < n; i++)
{
for (auto &edge : edges)
{
ll u = edge[0];
ll v = edge[1];
ll w = edge[2];
if (dist[u] != LLONG_MAX)
{
// if (dist[v] > dist[u] + w)
// {
ll z = dist[v];
dist[v] = min(dist[v], dist[u] + w);
if (dist[v] != z)
{
f = false;
par[v] = u;
}
// }
}
}
}
if (f)
{
cout << "NO\n";
}
else
{
ll x = 0;
for (ll i = 1; i <= n; i++)
{
if (par[i] != -1)
{
x = i;
break;
}
}
vector<ll> cycle;
unordered_set<ll> st;
while (st.find(x) == st.end())
{
cycle.push_back(x);
st.insert(x);
x = par[x];
}
cycle.push_back(x);
reverse(cycle.begin(), cycle.end());
cout << "YES\n";
unordered_set<ll> final;
for (auto &i : cycle)
{
cout << i << " ";
if (final.find(i) != final.end())
{
break;
}
final.insert(i);
}
}
}
Flight Routes
Thinking
Do djikstra,.. and keep track of all the distances...in a max heap.. if the size of the maxheap for the nth node is greater than n,.. then pop the largest element and insert the current distance if it is smaller than the top of the max heap
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
int n, m, k;
cin >> n >> m >> k;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
priority_queue<ll> bes[n + 1];
vector<pair<ll, ll>> adj[n + 1];
for (ll i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
}
bes[1].push(0);
pq.push({0, 1});
while (pq.size() > 0)
{
auto a = pq.top();
pq.pop();
if (a.first > bes[a.second].top())
continue;
for (auto &i : adj[a.second])
{
ll tmp = a.first + i.second;
if (bes[i.first].size() < k)
{
bes[i.first].push(tmp);
pq.push({tmp, i.first});
}
else if (tmp < bes[i.first].top())
{
bes[i.first].pop();
bes[i.first].push(tmp);
pq.push({tmp, i.first});
}
}
}
vector<ll> ans;
while (bes[n].size() > 0)
{
ans.push_back(bes[n].top());
bes[n].pop();
}
reverse(ans.begin(), ans.end());
for (auto a : ans)
cout << a << " ";
}
Round Trip II
Thinking
same as round trip,..except here the graph is directed
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll paret[100005];
ll colour[100005];
ll vis[100005];
vector<vector<ll>> adj(100005);
bool dfs(int node, int parent)
{
vis[node] = 1;
paret[node] = parent;
colour[node] = 1;
for (auto child : adj[node])
{
if (colour[child] == 1)
{
vector<ll> res;
ll x = node;
while (x != child)
{
res.push_back(x);
x = paret[x];
}
res.push_back(x);
// if(res[0]==res[res.size()-1])
// res.pop_back();
res.push_back(res[0]);
cout << res.size() << "\n";
reverse(res.begin(), res.end());
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
else if (colour[child] == 0)
{
bool temp = dfs(child, node);
if (temp == true)
{
vector<ll> res;
ll x = paret[child];
while (paret[x] != child)
{
res.push_back(x);
x = paret[x];
}
cout << res.size() << "\n";
reverse(res.begin(), res.end());
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
}
}
colour[node] = 2;
return false;
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
while (m--)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
// adj[y].push_back(x);
}
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 1)
{
continue;
}
// memset(colour,0,sizeof colour);
dfs(i, 0);
}
cout << "IMPOSSIBLE\n";
}
Course Schedule
Thinking
topological sort using vertex removal algorithm
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool comp(const pair<ll, ld> &a, const pair<ll, ld> &b)
{
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<ll> in_degree(n + 1, 0);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
in_degree[y]++;
}
queue<ll> q;
for (ll i = 1; i < n + 1; i++)
{
if (in_degree[i] == 0)
{
q.push(i);
}
}
vector<ll> topo_sort;
while (q.size())
{
ll x = q.front();
q.pop();
topo_sort.push_back(x);
bool f = true;
for (auto &i : adj[x])
{
in_degree[i]--;
if (in_degree[i] == 0)
{
q.push(i);
f = false;
}
}
// if(f)
// {
// cout<<"IMPOSSIBLE\n";
// exit(0);
// }
}
if (topo_sort.size() == n)
{
for (auto i : topo_sort)
{
cout << i << " ";
}
}
else
{
cout << "IMPOSSIBLE\n";
}
}
}
Longest Flight Route
Thinking
it is given that the graph is a DAG(Directed acyclic graph),.. so we can use DP
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<ll> dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<vector<ll>> &dp)
{
if (node == dest)
{
return {1, -1, 1};
}
if (!(((dp[node][0] == -1) && (dp[node][1] == -1)) && (dp[node][2] == -1)))
{
return dp[node];
}
ll f = 0;
ll dist = 0;
ll nextcity = -1;
for (auto &i : adj[node])
{
vector<ll> z = dfs(i, dest, adj, dp);
if (z[2] == 1)
{
f = 1;
if (dist < z[0])
{
dist = z[0];
nextcity = i;
}
}
}
return (dp[node] = {dist + 1, nextcity, f});
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
}
vector<vector<ll>> dp(n + 1, vector<ll>(3, -1));
ll x = 1;
if (dfs(1, n, adj, dp)[2] != 1)
{
cout << "IMPOSSIBLE\n";
}
else
{
cout << dfs(1, n, adj, dp)[0] << "\n";
ll x = 1;
while (dfs(x, n, adj, dp)[1] != -1)
{
cout << x << " ";
x = dfs(x, n, adj, dp)[1];
}
cout << x << "\n";
}
}
Game Routes
Thinking
again its a DAG,.. so we use dp
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll mod = (ll)(1e9 + 7);
pair<ll, ll> dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<pair<ll, ll>> &dp) // ways,possibel
{
if (node == dest)
{
return {1, 1};
}
if (!((dp[node].first == -1) && (dp[node].second == -1)))
{
return dp[node];
}
ll ways = 0;
ll f = 0;
for (auto &i : adj[node])
{
auto z = dfs(i, dest, adj, dp);
if (z.second == 1)
{
f = 1;
ways += z.first;
ways %= mod;
}
}
return (dp[node] = {ways, f});
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
}
vector<pair<ll, ll>> dp(n + 1, {-1, -1});
auto z = dfs(1, n, adj, dp);
cout << z.first << "\n";
}
Investigation
Thinking
state djikstra for each node,.. maintain the given four states: dist,ways,minc,maxc
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll mod = (ll)(1e9 + 7);
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
// vector<pair<ll, ll>> dist(n + 1, {LLONG_MAX, 0}); // dist,ways
vector<ll> dist(n + 1, LLONG_MAX);
vector<ll> ways(n + 1, 0);
vector<ll> minc(n + 1, 0);
vector<ll> maxc(n + 1, 0);
dist[1] = 0;
ways[1] = 1;
minc[1] = 1;
maxc[1] = 1;
pq.push({0, 1});
while (pq.size() > 0)
{
auto z = pq.top();
pq.pop();
ll u = z.second;
ll w = z.first;
if (dist[u] < w)
{
continue;
}
for (auto &i : adj[u])
{
ll v = i.first;
ll weight = i.second;
if (dist[v] > w + weight)
{
dist[v] = w + weight;
ways[v] = ways[u];
minc[v] = minc[u] + 1;
maxc[v] = maxc[u] + 1;
pq.push({dist[v], v});
}
else if (dist[v] == (w + weight))
{
// dist[v] = w + weight;
ways[v] += ways[u];
ways[v] %= mod;
minc[v] = min(minc[v], minc[u] + 1);
maxc[v] = max(maxc[v], maxc[u] + 1);
}
}
}
cout << dist[n] << " " << ways[n] << " " << minc[n] - 1 << " " << maxc[n] - 1 << "\n";
}
Planet Queries I
Thinking
use binary jumping i.e. for each node calculate findpar(x,k).. i.e. the 2^k th successor of node x. Now if we need to find the dth successor of the xth node, represent d as the sum of powers of 2. This is similar to binary lifting used to find the kth ancestor of a node in a tree.
Code
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll n, q;
// vector<vector<ll>> dp(2e5 + 1, vector<ll>(30, -1));
ll dp[200001][30];
ll findpar(ll node, ll k)
{
ll x = node;
for (ll i = 0; i < 30; i++)
{
if (k & (1ll << i))
{
// x = f(x, i, dp, par);
x = dp[x][i];
}
}
return x;
}
int main()
{
fastio;
cin >> n >> q;
for (ll i = 1; i <= n; i++)
{
cin >> dp[i][0];
}
for (ll i = 1; i < 30; i++)
{
for (ll j = 1; j <= n; j++)
{
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
while (q--)
{
ll a, b;
cin >> a >> b;
cout << findpar(a, b) << "\n";
}
}
Planet Queries II
Thinking
This is a successor graph,.. so it can be divided into components having a cycle and a paths pointing to the cycle so if the nodes belong to the same cycle,.. then the distance is (dfs number(v)-dfs number(u)+cyclelength)%cyclelength else if both are not part of any cycle,.. then if we jump from u by (dfs number(v)-dfs number(v)), and we reach v,.. then the answer is jump else its -1 now if one node is in a cycle and the other isnt then the one outside the cycle,.. we find the nearest cycle node to it using binary jumping and binary search let this closest cycle node be called interm(as in intermediate node) now dist = distance between u and interm + distance between interm and y(can be found using (dfs number(y)-dfs number(interm)+cyclelength)%cyclelength.. as shown int the above case)
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
void addno(ll i, unordered_set<ll> &done, vector<ll> &nextnode, vector<ll> &no)
{
if (done.find(i) != done.end())
return;
addno(nextnode[i], done, nextnode, no);
done.insert(i);
no[i] = no[nextnode[i]] - 1;
}
ll dp[200005][30];
ll findpar(ll node, ll k)
{
ll x = node;
for (ll i = 0; i < 30; i++)
{
if (k & (1ll << i))
{
// x = f(x, i, dp, par);
x = dp[x][i];
}
}
return x;
}
int main()
{
fastio;
ll n, q;
cin >> n >> q;
vector<ll> nextnode(n + 1);
for (ll i = 1; i <= n; i++)
{
cin >> nextnode[i];
dp[i][0] = nextnode[i];
}
vector<ll> vis(n + 1, 0);
for (ll i = 1; i < 30; i++)
{
for (ll j = 1; j <= n; j++)
{
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
// vector<ll> answer(n + 1, -1);
vector<vector<ll>> cycles;
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
unordered_set<ll> tempset;
vector<ll> tempvec;
ll x = i;
bool flag = true;
while (tempset.find(x) == tempset.end())
{
tempset.insert(x);
tempvec.push_back(x);
if (vis[x])
{
flag = false;
break;
}
x = nextnode[x];
}
if (!flag)
{
for (auto &i : tempvec)
vis[i] = 1;
continue;
}
ll z = find(tempvec.begin(), tempvec.end(), x) - tempvec.begin();
ll m = tempvec.size();
vector<ll> cycle;
for (ll i = z; i < m; i++)
{
vis[tempvec[i]] = 1;
cycle.push_back(tempvec[i]);
}
for (ll i = z - 1; i >= 0; i--)
{
vis[tempvec[i]] = 1;
}
cycles.push_back(cycle);
}
}
vector<ll> no(n + 1, -1);
unordered_set<ll> done;
vector<ll> cycleidx(n + 1, -1);
ll idx = 0;
for (auto &i : cycles)
{
ll c = 0;
for (auto &j : i)
{
no[j] = c++;
cycleidx[j] = idx;
done.insert(j);
}
idx++;
}
for (ll i = 1; i <= n; i++)
{
addno(i, done, nextnode, no);
}
// for (ll i = 1; i <= n; i++)
// cout << cycleidx[i] << " " << no[i] << "\n";
while (q--)
{
ll x, y;
cin >> x >> y;
if ((cycleidx[x] == cycleidx[y]) && ((cycleidx[x] != -1) && (cycleidx[y] != -1)))
{
ll b = cycles[cycleidx[x]].size();
cout << ((no[y] - no[x] + b) % b) << "\n";
}
else if ((cycleidx[x] == -1) || (cycleidx[y] == -1))
{
if ((cycleidx[x] == -1) && (cycleidx[y] == -1))
{
if (no[x] > no[y])
cout << "-1\n";
else
{
ll jump = no[y] - no[x];
if (findpar(x, jump) == y)
cout << jump << "\n";
else
cout << "-1\n";
}
}
else
{
// if (no[x] > no[y])
// {
if ((cycleidx[x] != -1) && (cycleidx[y] == -1))
cout << "-1\n";
else
{
ll lo = 0;
ll hi = n;
ll ans = -1;
while (lo <= hi)
{
ll mid = (lo + hi) / 2;
if (cycleidx[findpar(x, mid)] != -1)
{
ans = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
ll interm = findpar(x, ans);
if (cycleidx[interm] == cycleidx[y])
{
ll h = cycles[cycleidx[y]].size();
cout << ((no[interm] - no[x]) + ((no[y] - no[interm] + h) % h)) << "\n";
}
else
{
cout << "-1\n";
}
}
}
}
else
{
cout << "-1\n";
}
}
}
Planet Cycles
Thinking
this is again a successor graph,.. so we divide it into components having a cycle and paths pointing to the cycles,.. so we do dfs,.. and keep track of the dfs numbers for each node in the cycle,.. the answer is the cycle length.. for other nodes,.. let the node be x,..ans[x] = ans[nextnode[x]]+1
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n;
cin >> n;
vector<ll> nextnode(n + 1);
for (ll i = 1; i <= n + 1; i++)
{
cin >> nextnode[i];
}
vector<ll> vis(n + 1, 0);
vector<ll> answer(n + 1, -1);
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
unordered_set<ll> tempset;
vector<ll> tempvec;
ll x = i;
bool flag = true;
while (tempset.find(x) == tempset.end())
{
tempset.insert(x);
tempvec.push_back(x);
if (vis[x])
{
flag = false;
break;
}
x = nextnode[x];
}
ll z = find(tempvec.begin(), tempvec.end(), x) - tempvec.begin();
ll m = tempvec.size();
for (ll i = z; i < m; i++)
{
vis[tempvec[i]] = 1;
if (answer[tempvec[i]] == -1)
answer[tempvec[i]] = m - z;
}
for (ll i = z - 1; i >= 0; i--)
{
vis[tempvec[i]] = 1;
if (answer[tempvec[i]] == -1)
answer[tempvec[i]] = answer[tempvec[i + 1]] + 1;
}
}
}
for (ll i = 1; i <= n; i++)
cout << answer[i] << " ";
}
Road Reparation
Thinking
simple MST finding,.. I have implemented using kruskals algo
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<ll> ranq(100001);
vector<ll> par(100001);
void make_set(ll n)
{
for (ll i = 1; i <= n; i++)
{
ranq[i] = 1;
par[i] = i;
}
}
ll find_set(ll x)
{
if (par[x] == x)
{
return x;
}
par[x] = find_set(par[x]);
return par[x];
}
void union_set(ll a, ll b)
{
ll x = find_set(a);
ll y = find_set(b);
if (x == y)
return;
if (ranq[x] > ranq[y])
{
par[y] = x;
ranq[x] += ranq[y];
}
else
{
par[x] = y;
ranq[y] += ranq[x];
}
}
int32_t main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
make_set(n);
vector<pair<ll, pair<ll, ll>>> v;
while (m--)
{
ll a, b, c;
cin >> a >> b >> c;
v.push_back({c, {a, b}});
}
sort(v.begin(), v.end());
m = v.size();
ll cost = 0;
for (ll i = 0; i < m; i++)
{
ll x = v[i].second.first;
ll y = v[i].second.second;
ll w = v[i].first;
if (find_set(x) != find_set(y))
{
cost += w;
union_set(x, y);
}
}
if (ranq[find_set(1)] == n)
{
cout << cost << "\n";
}
else
{
cout << "IMPOSSIBLE\n";
}
}
}
Road Construction
Thinking
we use dsu,.. while merging two nodes,if their parents were same,.. we return false,.. otherwise return true hence if two nodes were merged whose parents were different,.. then we can see that the number of components decreases otherwise if theri parents are same,.. it remains unchanged
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll maxcomp = 1;
vector<ll> ranq(100001);
vector<ll> par(100001);
void make_set(ll n)
{
for (ll i = 1; i <= n; i++)
{
ranq[i] = 1;
par[i] = i;
}
}
ll find_set(ll x)
{
if (x == par[x])
return x;
par[x] = find_set(par[x]);
return par[x];
}
bool union_set(ll a, ll b)
{
ll x = find_set(a);
ll y = find_set(b);
if (x == y)
return false;
if (ranq[x] > ranq[y])
{
par[y] = x;
ranq[x] += ranq[y];
if (ranq[x] > maxcomp)
{
maxcomp = ranq[x];
}
return true;
}
else
{
par[x] = y;
ranq[y] += ranq[x];
if (ranq[y] > maxcomp)
{
maxcomp = ranq[y];
}
return true;
}
}
int32_t main()
{
fastio;
ll t = 1;
while (t--)
{
ll n, m;
cin >> n >> m;
make_set(n);
ll nocomp = n;
while (m--)
{
ll x, y;
cin >> x >> y;
bool res = union_set(x, y);
if (res)
{
nocomp--;
}
cout << nocomp << " " << maxcomp << "\n";
}
}
}
Flight Routes Check
Thinking
the question reduces itself to the simple problem of checking if the entire graph is a single stringly connected component or not we apply kosaraju's algorithm to find sccs for each scc ,.. we store the head node i.e. while doing the second dfs in the decreasing order of finish times if there are 2 or more sccs,.. we print head nodes of the first 2 SCCs
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &finish, ll &timer, vector<ll> &vis)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
finish[node] = timer++;
}
void dfs2(ll node, vector<ll> &vis, vector<vector<ll>> &adj)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs2(i, vis, adj);
}
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<vector<ll>> adjt(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adjt[y].push_back(x);
}
vector<ll> finish(n + 1, -1);
vector<ll> vis(n + 1, 0);
ll timer = 0;
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
vector<ll> ord(n);
for (ll i = 0; i < n; i++)
{
ord[i] = i + 1;
}
sort(ord.begin(), ord.end(), [&](ll a, ll b)
{ return (finish[a] > finish[b]); });
vis.clear();
vis.resize(n + 1, 0);
ll cnt = 0;
vector<ll> nodes;
for (ll i = 0; i < n; i++)
{
if (vis[ord[i]] == 0)
{
nodes.push_back(ord[i]);
cnt++;
dfs2(ord[i], vis, adjt);
}
}
if (cnt == 1)
{
cout << "YES\n";
}
else
{
cout << "NO\n";
cout << nodes[1] << " " << nodes[0] << "\n";
}
}
Planets and Kingdoms
Thinking
we perform kosaraju's algorithm and find the scc to which each planet belongs to,.. while performing the second dfs,.. we also mark the planets with the current position of the kingdom,.. which is denoted in the above code by the variable c declared in line 76
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &finish, ll &timer, vector<ll> &vis)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
finish[node] = timer++;
}
void dfs2(ll node, vector<ll> &vis, vector<vector<ll>> &adj, ll king, vector<ll> &kingdom)
{
vis[node] = 1;
kingdom[node] = king;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs2(i, vis, adj, king, kingdom);
}
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<vector<ll>> adjt(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adjt[y].push_back(x);
}
vector<ll> finish(n + 1, -1);
vector<ll> vis(n + 1, 0);
ll timer = 0;
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
vector<ll> ord(n);
for (ll i = 0; i < n; i++)
{
ord[i] = i + 1;
}
sort(ord.begin(), ord.end(), [&](ll a, ll b)
{ return (finish[a] > finish[b]); });
vis.clear();
vis.resize(n + 1, 0);
ll cnt = 0;
vector<ll> nodes;
vector<ll> kingdom(n + 1, -1);
ll c = 0;
for (ll i = 0; i < n; i++)
{
if (vis[ord[i]] == 0)
{
c++;
dfs2(ord[i], vis, adjt, c, kingdom);
}
}
cout << c << "\n";
for (ll i = 1; i <= n; i++)
{
cout << kingdom[i] << " ";
}
}
Giant Pizza
Thinking
this is a classical problem of 2-SAT recommended reading material: https://cp-algorithms.com/graph/2SAT.html
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int tval[200005];
vector<int> adj[200005], adj2[200005];
vector<int> v;
bool vis[200005];
void dfs(int s)
{
if (vis[s])
return;
vis[s] = 1;
for (auto i : adj[s])
dfs(i);
v.push_back(s);
}
int k = 0;
int comp[200005];
void dfs2(int s)
{
if (vis[s])
return;
vis[s] = 1;
comp[s] = k;
for (auto i : adj2[s])
dfs2(i);
}
int main()
{
// fastio;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
char x, y;
int a, b;
cin >> x >> a >> y >> b;
if (x == '-')
a = 2 * m - a + 1;
if (y == '-')
b = 2 * m - b + 1;
adj[2 * m - a + 1].push_back(b);
adj[2 * m - b + 1].push_back(a);
adj2[a].push_back(2 * m - b + 1);
adj2[b].push_back(2 * m - a + 1);
}
for (int i = 1; i <= 2 * m; i++)
{
if (!vis[i])
dfs(i);
}
memset(vis, 0, sizeof vis);
reverse(v.begin(), v.end());
for (auto i : v)
{
int x = i;
if (!vis[x])
{
k++;
dfs2(x);
}
}
for (ll i = 1; i <= m; i++)
{
if (comp[i] == comp[2 * m - i + 1])
{
cout << "IMPOSSIBLE\n";
return 0;
}
tval[i] = (comp[i] > comp[2 * m - i + 1]);
}
for (ll i = 1; i <= m; i++)
{
cout << ((tval[i]) ? '+' : '-') << " ";
}
}
Coin Collector
Thinking
we convert the given graph to a DAG,.. so the collector can visit one node os the DAG and collect all the coins which were originally present in the nodes which were converted to this node in the DAG to make it easier to implement SCC,.. I have made a class SCCmaker,.. u can go through the above code and save it as a template to easily implement conversion of a graph to a DAG in future :)
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
class SCCmaker
{
vector<vector<ll>> DAG;
vector<ll> info;
ll number_of_nodes;
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &vis, vector<ll> &order)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] != 1)
{
dfs(i, adj, vis, order);
}
}
order.push_back(node);
}
void dfs2(ll node, vector<vector<ll>> &revadj, vector<ll> &temp, vector<ll> &vis)
{
vis[node] = 1;
temp.push_back(node);
for (auto &i : revadj[node])
{
if (vis[i] == 0)
{
dfs2(i, revadj, temp, vis);
}
}
}
public:
SCCmaker(vector<vector<ll>> &adj, vector<ll> &information, ll (*combine)(vector<ll> &temp, vector<ll> &information), vector<pair<ll, ll>> &edges, ll n)
{
vector<ll> order;
vector<ll> vis(n + 1, 0);
for (ll i = 1; i <= n; i++)
{
if (!vis[i])
dfs(i, adj, vis, order);
}
reverse(order.begin(), order.end());
vector<ll> vis2(n + 1, 0);
vector<vector<ll>> revadj(n + 1);
for (auto &i : edges)
{
revadj[i.second].push_back(i.first);
}
vector<ll> parentset(n + 1, 0);
ll c = 0;
for (auto &i : order)
{
if (!vis2[i])
{
vector<ll> temp;
dfs2(i, revadj, temp, vis2);
ll z = temp.size();
for (ll j = 0; j < z; j++)
{
parentset[temp[j]] = c;
}
ll sum = combine(temp, information);
info.push_back(sum);
c++;
}
}
DAG.resize(c);
number_of_nodes = c;
for (auto &i : edges)
{
if (parentset[i.first] != parentset[i.second])
{
DAG[parentset[i.first]].push_back(parentset[i.second]);
}
}
}
vector<vector<ll>> getDAG()
{
return DAG;
}
vector<ll> getinfo()
{
return info;
}
ll get_numberofnodes()
{
return number_of_nodes;
}
};
ll combine(vector<ll> &temp, vector<ll> &information)
{
ll sum = 0;
for (auto &i : temp)
{
sum += information[i - 1];
}
return sum;
}
ll solve(ll node, vector<vector<ll>> &DAG, vector<ll> &DAGinfo, vector<ll> &dp)
{
ll res = 0;
if (dp[node] != -1)
return dp[node];
for (auto &i : DAG[node])
{
res = max(res, solve(i, DAG, DAGinfo, dp));
}
return dp[node] = (res + DAGinfo[node]);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<ll> val(n);
for (auto &i : val)
{
cin >> i;
}
vector<vector<ll>> adj(n + 1);
vector<pair<ll, ll>> edges;
for (ll i = 1; i <= m; i++)
{
ll x, y;
cin >> x >> y;
edges.push_back({x, y});
adj[x].push_back(y);
}
SCCmaker sccmaker(adj, val, combine, edges, n);
ll DAGnodes = sccmaker.get_numberofnodes();
vector<vector<ll>> DAG = sccmaker.getDAG();
vector<ll> DAGinfo = sccmaker.getinfo();
vector<ll> dp(DAGnodes + 1, -1);
ll res = 0;
for (ll i = 0; i < DAGnodes; i++)
{
res = max(res, solve(i, DAG, DAGinfo, dp));
}
cout << res << "\n";
}
Mail Delive
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
