Hello Codeforces, this is my first blog and here I have given my solution of the complete CSES Graph Algorithms section. [This](https://github.com/SamudraMitra/cses) is the github repo where I have pushed all the cpp files:↵
↵
↵
Counting Rooms↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs in a grid↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Labyrinth↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for path↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Building Roads↵
------------------↵
↵
<spoiler summary="Thinking">↵
do bfs and store the starting vertex of each bfs traversal↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Message Route↵
------------------↵
↵
<spoiler summary="Thinking">↵
do bfs and store parent↵
</spoiler>↵
↵
↵
<spoiler summary="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 << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Building Teams↵
------------------↵
↵
<spoiler summary="Thinking">↵
check if the graph can be divided into a bipartite graph using bfs.↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Round Trip↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Monsters↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
// }↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Shortest Routes I↵
------------------↵
↵
<spoiler summary="Thinking">↵
simple djikstra↵
</spoiler>↵
↵
↵
<spoiler summary="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] << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Shortest Routes II↵
------------------↵
↵
<spoiler summary="Thinking">↵
simple Floyd Warshall↵
</spoiler>↵
↵
↵
<spoiler summary="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]<<" ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
High Score↵
------------------↵
↵
<spoiler summary="Thinking">↵
negate the edge weights and use bellman ford to get the minimum negative score ,.. i.e. the max score in positive numbers↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Flight Discount↵
------------------↵
↵
<spoiler summary="Thinking">↵
use state djikstra↵
What is state djikstra you might ask:↵
↵
<spoiler summary="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.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Cycle Finding↵
------------------↵
↵
<spoiler summary="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 .↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
}↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Flight Routes↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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 << " ";↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Round Trip II↵
------------------↵
↵
<spoiler summary="Thinking">↵
same as round trip,..except here the graph is directed↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Course Schedule↵
------------------↵
↵
<spoiler summary="Thinking">↵
topological sort using vertex removal algorithm↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Longest Flight Route↵
------------------↵
↵
<spoiler summary="Thinking">↵
it is given that the graph is a DAG(Directed acyclic graph),.. so we can use DP↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Game Routes↵
------------------↵
↵
<spoiler summary="Thinking">↵
again its a DAG,.. so we use dp↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Investigation↵
------------------↵
↵
<spoiler summary="Thinking">↵
state djikstra for each node,.. maintain the given four states:↵
dist,ways,minc,maxc↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planet Queries I↵
------------------↵
↵
<spoiler summary="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.↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planet Queries II↵
------------------↵
↵
<spoiler summary="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)↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planet Cycles↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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] << " ";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Road Reparation↵
------------------↵
↵
<spoiler summary="Thinking">↵
simple MST finding,.. I have implemented using kruskals algo↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Road Construction↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Flight Routes Check↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planets and Kingdoms↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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] << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Giant Pizza↵
------------------↵
↵
<spoiler summary="Thinking">↵
this is a classical problem of 2-SAT↵
recommended reading material: https://cp-algorithms.com/graph/2SAT.html↵
</spoiler>↵
↵
↵
<spoiler summary="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]) ? '+' : '-') << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Coin Collector↵
------------------↵
↵
<spoiler summary="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 :)↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Mail Delivery↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for pathrecommended reading material: https://cp-algorithms.com/graph/euler_path.html↵
I have implemented the algorithm as described in the article above↵
</spoiler>↵
↵
↵
<spoiler summary="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> enddet<ll>> adj(n + 1);↵
vector<ll> deg(n + 1, 0);↵
for (ll i = 0; i <nm; i++)↵
{↵
for (ll j = 0; j < m; j++)↵
{↵
if (v[i][j] == 'A')ll x, y;↵
cin >> x >> y;↵
adj[x].insert(y);↵
adj[y].insert(x);↵
{deg[x]++;↵
deg[y]++;↵
}↵
st = {i, j};↵
}ack<ll> st;↵
for (ll i = 1; i <= n; i++)↵
{↵
if (v[i][j] == 'B'deg[i] % 2)↵
{↵
endd = {i, j}cout << "IMPOSSIBLE\n";↵
}return 0;↵
}↵
}↵
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;↵
qll> path;↵
st.push(st1);↵
while (qst.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)))↵
continue;↵
if ((v[nx][ny] != '#') && (vis[nx][nyst.top();↵
if (deg[x] == 0))↵
{↵
prev[nx][ny] = {x, y};↵
vis[nx][ny] = 1;↵
q.push({nx, ny}st.pop();↵
path.push_back(x);↵
}↵
}↵
}↵
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)else↵
{↵
↵
ll z = *(adj[x].begin());↵
{↵
res.push_back(curr);↵
curr = {prev[curr.first][curr.second]};↵
}↵
res.push_back(st);↵
↵
reverse(res.begin(), res.end());↵
// for(auto i: res)↵
// {↵
adj[x].erase(z);↵
// 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)adj[z].erase(x);↵
deg[x]--;↵
deg[z]--;↵
st.push(z);↵
}↵
}↵
if (path.size()=!= (res[i + 1].second))))↵
m + 1))↵
{↵
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 << "IMPOSSIBLE\n";↵
return 0;↵
}↵
for (auto &i : path)↵
}{↵
}↵
cout << direc << "\n";i << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthDe Bruijn Sequence↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for pathrecommended reading material: https://cses.fi/book/book.pdf#page=188↵
</spoiler>↵
↵
↵
<spoiler summary="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 >> mint main()↵
{↵
fastio;↵
ll n;↵
cin >> n;↵
if (n == 1)↵
{↵
cout << "01\n";↵
return 0;↵
}↵
ll N = (1 << (n - 1)) - 1;↵
↵
vector<string> v(n);↵
for (auto &i : v)↵
cin >> i;↵
pair<ll, ll> st;↵
pair<ll, ll> enddvector<ll>> adj(N + 1);↵
vector<ll> indeg(N + 1);↵
vector<ll> outdeg(N + 1);↵
for (ll i = 0; i < n= 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};↵
}↵
}ll num1 = (i * 2) % (1 << (max(0ll, (n - 1))));↵
ll num2 = ((i * 2) + 1) % (1 << (max(0ll, (n - 1))));↵
// cout << i << " " << num1 << " " << num2 << "\n";↵
adj[i].push_back(num1);↵
adj[i].push_back(num2);↵
outdeg[i] += 2;↵
indeg[num1]++;↵
indeg[num2]++;↵
}↵
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;↵
qll> path;↵
stack<ll> st;↵
st.push(st0);↵
while (qst.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];↵
st.top();↵
if (!(inrange(nx, ny, n, m)))↵
continue;↵
if ((v[nx][nydeg[x] !== '#'0) && (vis[nx][nyoutdeg[x] == 0))↵
{↵
prev[nx][ny] = {x, y};↵
vis[nx][ny] = 1;↵
q.push({nx, ny}ath.push_back(x);↵
}st.pop();↵
}↵
}↵
if (vis[endd.first][endd.second] == 0) else↵
{↵
{↵
cout << "NO\n";↵
return 0;↵
}↵
vector<pair<ll, ll>> res;↵
// res.push ll k = adj[x].back();↵
adj[x].pop_back(endd);↵
pair<ll, ll> curr = endd;↵
while (curr != st) indeg[k]--;↵
outdeg[x]--;↵
{↵
resst.push_back(curr(k);↵
curr = {prev[curr.first][curr.second]};↵
}↵
res.push_back(st);↵
}↵
}↵
reverse(respath.begin(), respath.end());↵
// for (autoi: res&i : path)↵
// {↵
// cout<<i.first<<" "<<i.second<<"\n";↵
// }↵
cout << "YES\n";↵
cout << res.size() - 1 << "\n"; << i << " ";↵
// }↵
stringdirecs = "";↵
for (ll i = 0; i <(ll)(res.size()n - 1); i++)↵
{↵
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))↵
{↵
direc += 'D'; res += '0';↵
}↵
ll m = path.size();↵
↵
for (ll i = 0; i < m - 1; i++)↵
}{↵
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].secondpath[i + 1] == ((path[i] * 2) % (1 << (max(0ll, (n - 1))))))↵
{↵
direcs += 'R0';↵
}↵
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))↵
{↵
direcs += 'U1';↵
}↵
else↵
{↵
direc += 'L';↵
}}↵
// reverse(res.begin(), res.end());↵
cout << res << "\n";↵
// for (auto &i : path)↵
// {↵
}↵
// cout << direc << "\n";i << " ";↵
// }↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinTeleporters Path↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for paththis is a classic problem of finding the euler path↵
recommended reading material: https://cp-algorithms.com/graph/euler_path.html↵
I have implemented the algorithm as described in the article above↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
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;↵
pair<ll, ll> st;↵
pair<ll, ll> endd;↵
vector<ll>> adj(n + 1);↵
vector<ll> indeg(n + 1, 0);↵
vector<ll> outdeg(n + 1, 0);↵
for (ll i = 0; i <nm; i++)↵
{↵
for (ll j = 0; j < m; j++)↵
{↵
if (v[i][j] == 'A') ll x, y;↵
cin >> x >> y;↵
adj[x].push_back(y);↵
indeg[y]++;↵
{outdeg[x]++;↵
}↵
st = {i, j};↵
for (ll i = 2; i < n; i++)↵
}{↵
if (v[i][j] == 'B'indeg[i] != outdeg[i])↵
{↵
endd = {i, j}cout << "IMPOSSIBLE\n";↵
} return 0;↵
}↵
}↵
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())↵
}↵
if (((outdeg[1] - indeg[1]) != 1) || ((outdeg[n] - indeg[n]) != -1))↵
{↵
ll x = q.front().first;↵
ll y = q.front().second cout << "IMPOSSIBLE\n";↵
return 0;↵
q.pop();}↵
for (ll j = 0; j < 4; j++)↵
{stack<ll> st;↵
st.push(1);↵
ll nx = x + dx[j];↵
ll ny = y + dy[j];↵
if (!(inrange(nx, ny, n, m)))↵
continuevector<ll> path;↵
while (st.size() > 0)↵
{↵
ll z = st.top();↵
if ((v[nx][nyindeg[z] !== '#'0) && (vis[nx][nyoutdeg[z] == 0))↵
{↵
prev[nx][ny] = {x, y};↵
vis[nx][ny] = 1ath.push_back(z);↵
q.push({nx, ny}st.pop();↵
}↵
}↵
}↵
if (vis[endd.first][endd.second] == 0)↵
{↵
cout << "NO\n";↵
return 0;↵
else↵
{↵
}↵
vector<pair<ll, ll>> res;↵
// res.push_back(endd);↵
pair<ll, ll> curr = endd;↵
while (curr != st)↵
ll m = adj[z].size();↵
{↵
resst.push_back(curr(adj[z][m - 1]);↵
curr = {prev[curr.first][curr.second]};↵
}↵
res.push_back(st);↵
↵
reverse(res.begin(), res.end());↵
// for(auto i: res)↵
// {↵
adj[z].pop_back();↵
// cout<<i.first<<" "<<i.second<<"\n"deg[z]--;↵
// }↵
cout << "YES\n";↵
cout << res.size() - 1 << "\n";↵
string direc = "";↵
for (ll i = 0; i < (ll)(res.size() - 1); i++)↵
indeg[adj[z][m - 1]]--;↵
}↵
{}↵
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)path.size() =!= (res[i + 1].second))m + 1))↵
{↵
direc += 'D';↵
}↵
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))↵
{↵
direc += 'R'cout << "IMPOSSIBLE\n";↵
return 0;↵
}↵
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"; reverse(path.begin(), path.end());↵
for (auto &i : path)↵
{↵
cout << i << " ";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthHamiltonian Flights↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for pathit is the simple backtracking implementation of number of hamiltonian paths↵
a mask variable is used in dfs to keep track of the nodes visited,.. if we reach the node n and the mask is 0(i.e. all the nodes are visited) then this counts as a valid path otherwise if the mask is not 0,..then it is not a valid path,.. and we return 0↵
we use a DP to memoize the results↵
</spoiler>↵
↵
↵
<spoiler summary="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++)↵
#define MOD 1000000007↵
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"// ll mod = (ll)(1e9 + 7);↵
// vector<vector<int>> dp((1 << 21), vector<int>(21, -1));↵
ll dp[1 << 21][22];↵
vector<int> adj[22];↵
int n;↵
ll dfs(int mask, int node)↵
{↵
mask = mask ^ (1 << (node));↵
if ((mask == 0) && (node == (n - 1)))↵
{↵
return 1;↵
}↵
if (node == (n - 1))↵
{↵
return 0;↵
}↵
if (dp[mask][node] != -1)↵
{↵
return dp[mask][node];↵
}↵
// ll res = 0;↵
// dp[mask][node] = 0;↵
ll res = 0;↵
for (auto &i : adj[node])↵
{↵
if ((1ll << (i)) & mask)↵
{↵
res += dfs(mask, i);↵
res %= MOD;↵
}↵
}↵
return (dp[mask][node] = res);↵
}↵
int main()↵
{↵
fastio;↵
int m;↵
cin >> n >> m;↵
for (int i = 0; i < m; i++)↵
{↵
int x, y;↵
cin >> x >> y;↵
x--;↵
y--;↵
adj[x].push_back(y);↵
}↵
memset(dp, -1, sizeof(dp));↵
cout << dfs((1 << n) - 1, 0);↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthKnight's Tour↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for pathhere also we use backtracking,.. but we need to find only one solution.. so↵
instead of randomly choosing the next square for the knight to move,..↵
we sort the available squares according to the number of squares available to go from them in a non increasing order. This allows us to always visit the square from which we have the maximum chance of having a next place to move the knight to and hence optimizes the solution↵
PS: without this optimization,. the code will give tle↵
</spoiler>↵
↵
↵
<spoiler summary="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";const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};↵
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};↵
ll board[8][8];↵
bool issafe(int x, int y)↵
{↵
return (((0 <= x) && (x < 8)) && ((0 <= y) && (y < 8)));↵
}↵
int deg(ll x, ll y)↵
{↵
int s = 0;↵
for (ll i = 0; i < 8; i++)↵
{↵
ll nx = x + dx[i];↵
ll ny = y + dy[i];↵
if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] != -1))↵
s++;↵
}↵
return s;↵
}↵
bool dfs(int x, int y, int move)↵
{↵
board[x][y] = move;↵
if (move == 64)↵
{↵
return true;↵
}↵
vector<vector<int>> vec;↵
for (int i = 0; i < 8; i++)↵
{↵
int nx = x + dx[i];↵
int ny = y + dy[i];↵
if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] == 0))↵
{↵
int d = deg(nx, ny);↵
vec.push_back({d, nx, ny});↵
}↵
}↵
sort(vec.begin(), vec.end());↵
for (auto &i : vec)↵
{↵
if (dfs(i[1], i[2], move + 1))↵
return true;↵
}↵
board[x][y] = 0;↵
return false;↵
}↵
int main()↵
{↵
fastio;↵
ll x, y;↵
cin >> y >> x;↵
x--;↵
y--;↵
memset(board, 0, sizeof(board));↵
bool res = dfs(x, y, 1);↵
for (auto &i : board)↵
{↵
for (auto &j : i)↵
{↵
cout << j << " ";↵
}↵
cout << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthDownload Speed↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for paththis is a problem of finding the maximum flow in a graph↵
this is solved by implementing the ford fulkerson algorithm↵
recommended reading material: https://cses.fi/book/book.pdf#page=191↵
I personally recommend to use the scaling algorithm to find paths for the ford fulkerson algorithm as it is easier to implement scaling algorithm: https://cses.fi/book/book.pdf#page=195↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
boolinrange(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 << direcdfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis)↵
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 1; i <= dest; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
int main()↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));↵
ll sum = 0;↵
for (ll i = 0; i < m; i++)↵
{↵
ll x, y, w;↵
cin >> x >> y >> w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
}↵
adj[x][y] += w;↵
adj[y][x] = 0;↵
sum += w;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + 1, 0);↵
bool f = dfs(1, n, adj, path, sum, vis);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll k = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
cout << ans << "\n";↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthPolice Chase↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for paththis is a problem of the finding the minimum cut↵
this is implemented using the ford fulkerson algorithm↵
it is strongly recommended to either solve or read the editorial of download speed problem proceeding↵
recommended reading material: https://cses.fi/book/book.pdf#page=195↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
boolinrange(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";dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)↵
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 1; i <= n; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis, n))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)↵
{↵
visited[node] = 1;↵
left.push_back(node);↵
for (ll i = 1; i <= n; i++)↵
{↵
if (visited[i])↵
continue;↵
if (og[node][i] <= 0)↵
continue;↵
dfs2(i, og, left, visited, n);↵
}↵
}↵
int main()↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));↵
vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));↵
ll sum = 0;↵
for (ll i = 0; i < m; i++)↵
{↵
ll x, y;↵
ll w = 1;↵
cin >> x >> y;↵
og[x][y] = w;↵
og[y][x] = w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
adj[y][x] = 0;↵
}↵
adj[x][y] += w;↵
adj[y][x] += w;↵
sum += w;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + 1, 0);↵
bool f = dfs(1, n, adj, path, sum, vis, n);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll k = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
cout << ans << "\n";↵
vector<ll> left;↵
vector<ll> visited(n + 1, 0);↵
dfs2(1, adj, left, visited, n);↵
unordered_set<ll> st;↵
for (auto &i : left)↵
st.insert(i);↵
for (auto &i : left)↵
{↵
for (ll j = 1; j <= n; j++)↵
{↵
if (((og[i][j] == 1) && (adj[i][j] == 0)) && (st.find(j) == st.end()))↵
{↵
cout << i << " " << j << "\n";↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthSchool Dance↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for paththis is a problem of finding the maximum matching↵
recommended reading material: https://cses.fi/book/book.pdf#page=197↵
I have implemented this article in the above code↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
boolinrange(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";dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)↵
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 0; i <= n; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis, n))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)↵
{↵
visited[node] = 1;↵
left.push_back(node);↵
for (ll i = 0; i <= n; i++)↵
{↵
if (visited[i])↵
continue;↵
// if (og[node][i] == -1)↵
// continue;↵
// if (og[node][i] == 0)↵
// continue;↵
if (og[node][i] <= 0)↵
continue;↵
dfs2(i, og, left, visited, n);↵
}↵
}↵
int main()↵
{↵
fastio;↵
ll n, m, k;↵
cin >> n >> m >> k;↵
vector<vector<ll>> adj(n + m + 2, vector<ll>(n + m + 2, -1));↵
vector<vector<ll>> og(n + m + 2, vector<ll>(n + m + 2, -1));↵
ll sum = 0;↵
for (ll i = 0; i < k; i++)↵
{↵
ll x, y;↵
ll w = 1;↵
cin >> x >> y;↵
y += n;↵
// y += 500;↵
og[x][y] = w;↵
// og[y][x] = w;↵
// og[y][x] = w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
// adj[y][x] = 0;↵
}↵
adj[x][y] = w;↵
adj[y][x] = 0;↵
sum += w;↵
}↵
for (ll i = 1; i <= n; i++)↵
{↵
adj[0][i] = 1;↵
og[0][i] = 1;↵
}↵
for (ll i = n + 1; i <= n + m; i++)↵
{↵
adj[i][n + m + 1] = 1;↵
og[i][n + m + 1] = 1;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + m + 2, 0);↵
bool f = dfs(0, n + m + 1, adj, path, sum, vis, n + m + 1);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll z = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
// for (ll i = 0; i <= n + m + 1; i++)↵
// {↵
// for (ll j = 0; j <= n + m + 1; j++)↵
// {↵
// cout << adj[i][j] << " ";↵
// }↵
// cout << "\n";↵
// }↵
cout << ans << "\n";↵
vector<ll> left;↵
// vector<ll> visited(n + m + 2, 0);↵
// dfs2(0, adj, left, visited, n + m + 1);↵
for (ll i = 1; i <= n; i++)↵
{↵
left.push_back(i);↵
}↵
unordered_set<ll> st;↵
for (auto &i : left)↵
{↵
st.insert(i);↵
}↵
for (auto &i : left)↵
{↵
for (ll j = n + 1; j <= n + m; j++)↵
{↵
if (((og[i][j] == 1) && (adj[i][j] == 0)))↵
{↵
cout << i << " " << j - n << "\n";↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
LabyrinthDistinct Routes↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for path↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
this is a problem of finding the maximum flow again↵
read this: https://cses.fi/book/book.pdf#page=196↵
this article helps you to find the length of the path↵
now to find the path.. we do this:↵
start from vertex 1↵
go through all the edges,.. and check if there is an edge,.. whose reverse edge(that we artificially create in ford fulkerson algorithm) has a value,.. and this edge has value 0↵
this means that this edge is included in the max flow path↵
we coninue this till we reach the end↵
finally we print the answer.↵
We maintain a set of pairs to make sure we don't consider an edge twice↵
</spoiler>↵
↵
↵
<spoiler summary="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 dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)↵
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 1; i <= n; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis, n))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
// void dfs2(ll node, vector<vector<ll>> &adj, vector<vector<ll>> &og, ll n, set<pair<ll, ll>> &st)↵
// {↵
// if (node != n)↵
// cout << node << " ";↵
// else if (node == n)↵
// cout << node << "\n";↵
// for (ll i = 1; i <= n; i++)↵
// {↵
// if (((adj[node][i] == 0) && (og[node][i] == 1)) && (st.find({node, i}) == st.end()))↵
// {↵
// st.insert({node, i});↵
// dfs2(i, adj, og, n, st);↵
// }↵
// }↵
// }↵
// bool dfs2(ll node, ll n, vector<vector<ll>> &adj, vector<vector<ll>> &og, vector<vector<ll>> &paths)↵
// {↵
// for (ll i = 1; i <= n; i++)↵
// {↵
// if ((adj[node][i] == 0) && (og[node][i] == 1))↵
// {↵
↵
// }↵
// }↵
// }↵
int main()↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));↵
vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));↵
ll sum = 0;↵
for (ll i = 0; i < m; i++)↵
{↵
ll x, y;↵
ll w = 1;↵
cin >> x >> y;↵
og[x][y] = w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
}↵
adj[x][y] = w;↵
if (adj[y][x] == -1)↵
adj[y][x] = 0;↵
sum += w;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + 1, 0);↵
bool f = dfs(1, n, adj, path, sum, vis, n);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll z = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
cout << ans << "\n";↵
set<pair<ll, ll>> ed;↵
// unordered_set<ll> ed;↵
for (ll i = 0; i < ans; i++)↵
{↵
vector<ll> v = {1};↵
int x = 1;↵
while (x != n)↵
{↵
for (ll i = 1; i <= n; i++)↵
{↵
if (((adj[x][i] == 0) && (og[x][i] == 1)) && (ed.find({x, i}) == ed.end()))↵
{↵
v.push_back(i);↵
ed.insert({x, i});↵
x = i;↵
break;↵
}↵
}↵
}↵
cout << v.size() << "\n";↵
for (auto i : v)↵
cout << (i) << " ";↵
cout << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
I hope that you will find these helpful, and will also find it in your hearts to forgive any mistake which might have crept in unknowingly. Also, any feedback is welcome.↵
↵
Peace!!
↵
↵
Counting Rooms↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs in a grid↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Labyrinth↵
------------------↵
↵
<spoiler summary="Thinking">↵
used simple bfs and stored parent for path↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Building Roads↵
------------------↵
↵
<spoiler summary="Thinking">↵
do bfs and store the starting vertex of each bfs traversal↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Message Route↵
------------------↵
↵
<spoiler summary="Thinking">↵
do bfs and store parent↵
</spoiler>↵
↵
↵
<spoiler summary="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 << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Building Teams↵
------------------↵
↵
<spoiler summary="Thinking">↵
check if the graph can be divided into a bipartite graph using bfs.↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Round Trip↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Monsters↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
// }↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Shortest Routes I↵
------------------↵
↵
<spoiler summary="Thinking">↵
simple djikstra↵
</spoiler>↵
↵
↵
<spoiler summary="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] << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Shortest Routes II↵
------------------↵
↵
<spoiler summary="Thinking">↵
simple Floyd Warshall↵
</spoiler>↵
↵
↵
<spoiler summary="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]<<" ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
High Score↵
------------------↵
↵
<spoiler summary="Thinking">↵
negate the edge weights and use bellman ford to get the minimum negative score ,.. i.e. the max score in positive numbers↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Flight Discount↵
------------------↵
↵
<spoiler summary="Thinking">↵
use state djikstra↵
What is state djikstra you might ask:↵
↵
<spoiler summary="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.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Cycle Finding↵
------------------↵
↵
<spoiler summary="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 .↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
}↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Flight Routes↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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 << " ";↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Round Trip II↵
------------------↵
↵
<spoiler summary="Thinking">↵
same as round trip,..except here the graph is directed↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Course Schedule↵
------------------↵
↵
<spoiler summary="Thinking">↵
topological sort using vertex removal algorithm↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Longest Flight Route↵
------------------↵
↵
<spoiler summary="Thinking">↵
it is given that the graph is a DAG(Directed acyclic graph),.. so we can use DP↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Game Routes↵
------------------↵
↵
<spoiler summary="Thinking">↵
again its a DAG,.. so we use dp↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Investigation↵
------------------↵
↵
<spoiler summary="Thinking">↵
state djikstra for each node,.. maintain the given four states:↵
dist,ways,minc,maxc↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planet Queries I↵
------------------↵
↵
<spoiler summary="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.↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planet Queries II↵
------------------↵
↵
<spoiler summary="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)↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planet Cycles↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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] << " ";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Road Reparation↵
------------------↵
↵
<spoiler summary="Thinking">↵
simple MST finding,.. I have implemented using kruskals algo↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Road Construction↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Flight Routes Check↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Planets and Kingdoms↵
------------------↵
↵
<spoiler summary="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↵
</spoiler>↵
↵
↵
<spoiler summary="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] << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Giant Pizza↵
------------------↵
↵
<spoiler summary="Thinking">↵
this is a classical problem of 2-SAT↵
recommended reading material: https://cp-algorithms.com/graph/2SAT.html↵
</spoiler>↵
↵
↵
<spoiler summary="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]) ? '+' : '-') << " ";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Coin Collector↵
------------------↵
↵
<spoiler summary="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 :)↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Mail Delivery↵
------------------↵
↵
<spoiler summary="Thinking">↵
I have implemented the algorithm as described in the article above↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
{↵
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));↵
}↵
ll dx[] = {1, 0, -1, 0};↵
ll dy[] = {0, 1, 0, -1};↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
for (auto &i : v)↵
cin >> i;↵
pair<ll, ll> st;↵
pair<ll, ll> endd
vector<ll> deg(n + 1, 0);↵
for (ll i = 0; i <
{↵
{↵
if (v[i][j] == 'A')
cin >> x >> y;↵
adj[x].insert(y);↵
adj[y].insert(x);↵
deg[y]++;↵
}↵
st
}
for (ll i = 1; i <= n; i++)↵
{↵
if (
}↵
}↵
vector<
vector<vector<ll>> vis(n, vector<ll>(m, 0));↵
vis[st.first][st.second] = 1;↵
queue<pair<ll, ll>> q;↵
q
st.push(
while (
{↵
ll x =
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
if (deg[x] == 0)
vis[nx][ny] = 1;↵
q.push({nx, ny}
path.push_back(x);↵
}↵
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)
{↵
↵
ll z = *(adj[x].begin());↵
curr = {prev[curr.first][curr.second]};↵
}↵
res.push_back(st);↵
↵
reverse(res.begin(), res.end());↵
// for(auto i: res)↵
// {↵
// }↵
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)
deg[x]--;↵
deg[z]--;↵
st.push(z);↵
}↵
}↵
if (path.size()
{↵
}↵
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))↵
{↵
direc += 'U';↵
}↵
else↵
{↵
direc += 'L';
return 0;↵
}↵
for (auto &i : path)↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
{↵
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
{↵
fastio;↵
ll n;↵
cin >> n;↵
if (n == 1)↵
{↵
cout << "01\n";↵
return 0;↵
}↵
ll N = (1 << (n - 1)) - 1;↵
for (auto &i : v)↵
cin >> i;↵
pair<ll, ll> st;↵
pair<ll, ll> endd
vector<ll> indeg(N + 1);↵
vector<ll> outdeg(N + 1);↵
for (ll i = 0; i <
{↵
{↵
if (v[i][j] == 'A')↵
{↵
st = {i, j};↵
}↵
if (v[i][j] == 'B')↵
{↵
endd = {i, j};↵
}↵
}
ll num2 = ((i * 2) + 1) % (1 << (max(0ll, (n - 1))));↵
// cout << i << " " << num1 << " " << num2 << "\n";↵
adj[i].push_back(num1);↵
adj[i].push_back(num2);↵
outdeg[i] += 2;↵
indeg[num1]++;↵
indeg[num2]++;↵
}↵
vector<
vector<vector<ll>> vis(n, vector<ll>(m, 0));↵
vis[st.first][st.second] = 1;↵
queue<pair<ll, ll>> q;↵
q
stack<ll> st;↵
st.push(
while (
{↵
ll x =
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 (
continue;↵
if ((v[nx][ny
vis[nx][ny] = 1;↵
q.push({nx, ny}
}↵
return 0;↵
}↵
vector<pair<ll, ll>> res;↵
// res.push
adj[x].pop_back(
while (curr != st)
outdeg[x]--;↵
}↵
res.push_back(st);↵
}↵
reverse(
// for (auto
// {↵
// cout
// }↵
cout << "YES\n";↵
cout << res.size() - 1 << "\n";
// }↵
string
for (ll i = 0; i <
{↵
{↵
direc += 'D';
}↵
ll m = path.size();↵
↵
for (ll i = 0; i < m - 1; i++)↵
{↵
}↵
else
{↵
}↵
{↵
direc += 'L';↵
}
// reverse(res.begin(), res.end());↵
cout << res << "\n";↵
// for (auto &i : path)↵
// {↵
// }↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
recommended reading material: https://cp-algorithms.com/graph/euler_path.html↵
I have implemented the algorithm as described in the article above↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
{↵
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));↵
}↵
ll dx[] = {1, 0, -1, 0};↵
ll dy[] = {0, 1, 0, -1};↵
int main()↵
{↵
fastio;↵
{↵
fastio;↵
ll t = 1;↵
// cin >> t;↵
while (t--)↵
{↵
ll n, m;↵
cin >> n >> m;↵
for (auto &i : v)↵
cin >> i;↵
pair<ll, ll> st;↵
pair<ll, ll> endd;↵
vector<ll> indeg(n + 1, 0);↵
vector<ll> outdeg(n + 1, 0);↵
for (ll i = 0; i <
{↵
{↵
if (v[i][j] == 'A')
cin >> x >> y;↵
adj[x].push_back(y);↵
indeg[y]++;↵
}↵
if (
{↵
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())↵
if (((outdeg[1] - indeg[1]) != 1) || ((outdeg[n] - indeg[n]) != -1))↵
ll y = q.front().second
return 0;↵
{
st.push(1);↵
ll ny = y + dy[j];↵
if (!(inrange(nx, ny, n, m)))↵
continue
while (st.size() > 0)↵
{↵
ll z = st.top();↵
if ((
{↵
p
vis[nx][ny] = 1
}↵
}↵
if (vis[endd.first][endd.second] == 0)↵
{↵
cout << "NO\n";↵
return 0;↵
{↵
// res.push_back(endd);↵
pair<ll, ll> curr = endd;↵
while (curr != st)↵
↵
reverse(res.begin(), res.end());↵
// for(auto i: res)↵
// {↵
cout << "YES\n";↵
cout << res.size() - 1 << "\n";↵
string direc = "";↵
for (ll i = 0; i < (ll)(res.size() - 1); i++)↵
}↵
if (
{↵
}↵
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))↵
{↵
direc += 'R'
return 0;↵
}↵
{↵
direc += 'U';↵
}↵
else↵
{↵
direc += 'L';↵
}↵
}↵
cout << direc << "\n";
for (auto &i : path)↵
{↵
cout << i << " ";↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
a mask variable is used in dfs to keep track of the nodes visited,.. if we reach the node n and the mask is 0(i.e. all the nodes are visited) then this counts as a valid path otherwise if the mask is not 0,..then it is not a valid path,.. and we return 0↵
we use a DP to memoize the results↵
</spoiler>↵
↵
↵
<spoiler summary="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++)↵
#define MOD 1000000007↵
ll gcd(ll a, ll b)↵
{↵
return b == 0 ? a : gcd(b, a % b);↵
}↵
{↵
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"
// vector<vector<int>> dp((1 << 21), vector<int>(21, -1));↵
ll dp[1 << 21][22];↵
vector<int> adj[22];↵
int n;↵
ll dfs(int mask, int node)↵
{↵
mask = mask ^ (1 << (node));↵
if ((mask == 0) && (node == (n - 1)))↵
{↵
return 1;↵
}↵
if (node == (n - 1))↵
{↵
return 0;↵
}↵
if (dp[mask][node] != -1)↵
{↵
return dp[mask][node];↵
}↵
// ll res = 0;↵
// dp[mask][node] = 0;↵
ll res = 0;↵
for (auto &i : adj[node])↵
{↵
if ((1ll << (i)) & mask)↵
{↵
res += dfs(mask, i);↵
res %= MOD;↵
}↵
}↵
return (dp[mask][node] = res);↵
}↵
int main()↵
{↵
fastio;↵
int m;↵
cin >> n >> m;↵
for (int i = 0; i < m; i++)↵
{↵
int x, y;↵
cin >> x >> y;↵
x--;↵
y--;↵
adj[x].push_back(y);↵
}↵
memset(dp, -1, sizeof(dp));↵
cout << dfs((1 << n) - 1, 0);↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
instead of randomly choosing the next square for the knight to move,..↵
we sort the available squares according to the number of squares available to go from them in a non increasing order. This allows us to always visit the square from which we have the maximum chance of having a next place to move the knight to and hence optimizes the solution↵
PS: without this optimization,. the code will give tle↵
</spoiler>↵
↵
↵
<spoiler summary="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);↵
}↵
{↵
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";
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};↵
ll board[8][8];↵
bool issafe(int x, int y)↵
{↵
return (((0 <= x) && (x < 8)) && ((0 <= y) && (y < 8)));↵
}↵
int deg(ll x, ll y)↵
{↵
int s = 0;↵
for (ll i = 0; i < 8; i++)↵
{↵
ll nx = x + dx[i];↵
ll ny = y + dy[i];↵
if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] != -1))↵
s++;↵
}↵
return s;↵
}↵
bool dfs(int x, int y, int move)↵
{↵
board[x][y] = move;↵
if (move == 64)↵
{↵
return true;↵
}↵
vector<vector<int>> vec;↵
for (int i = 0; i < 8; i++)↵
{↵
int nx = x + dx[i];↵
int ny = y + dy[i];↵
if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] == 0))↵
{↵
int d = deg(nx, ny);↵
vec.push_back({d, nx, ny});↵
}↵
}↵
sort(vec.begin(), vec.end());↵
for (auto &i : vec)↵
{↵
if (dfs(i[1], i[2], move + 1))↵
return true;↵
}↵
board[x][y] = 0;↵
return false;↵
}↵
int main()↵
{↵
fastio;↵
ll x, y;↵
cin >> y >> x;↵
x--;↵
y--;↵
memset(board, 0, sizeof(board));↵
bool res = dfs(x, y, 1);↵
for (auto &i : board)↵
{↵
for (auto &j : i)↵
{↵
cout << j << " ";↵
}↵
cout << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
this is solved by implementing the ford fulkerson algorithm↵
recommended reading material: https://cses.fi/book/book.pdf#page=191↵
I personally recommend to use the scaling algorithm to find paths for the ford fulkerson algorithm as it is easier to implement scaling algorithm: https://cses.fi/book/book.pdf#page=195↵
</spoiler>↵
↵
↵
<spoiler summary="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
{↵
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
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 1; i <= dest; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
int main()↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));↵
ll sum = 0;↵
for (ll i = 0; i < m; i++)↵
{↵
ll x, y, w;↵
cin >> x >> y >> w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
}↵
adj[x][y] += w;↵
adj[y][x] = 0;↵
sum += w;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + 1, 0);↵
bool f = dfs(1, n, adj, path, sum, vis);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll k = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
cout << ans << "\n";↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
this is implemented using the ford fulkerson algorithm↵
it is strongly recommended to either solve or read the editorial of download speed problem proceeding↵
recommended reading material: https://cses.fi/book/book.pdf#page=195↵
</spoiler>↵
↵
↵
<spoiler summary="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
{↵
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";
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 1; i <= n; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis, n))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)↵
{↵
visited[node] = 1;↵
left.push_back(node);↵
for (ll i = 1; i <= n; i++)↵
{↵
if (visited[i])↵
continue;↵
if (og[node][i] <= 0)↵
continue;↵
dfs2(i, og, left, visited, n);↵
}↵
}↵
int main()↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));↵
vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));↵
ll sum = 0;↵
for (ll i = 0; i < m; i++)↵
{↵
ll x, y;↵
ll w = 1;↵
cin >> x >> y;↵
og[x][y] = w;↵
og[y][x] = w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
adj[y][x] = 0;↵
}↵
adj[x][y] += w;↵
adj[y][x] += w;↵
sum += w;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + 1, 0);↵
bool f = dfs(1, n, adj, path, sum, vis, n);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll k = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < k - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
cout << ans << "\n";↵
vector<ll> left;↵
vector<ll> visited(n + 1, 0);↵
dfs2(1, adj, left, visited, n);↵
unordered_set<ll> st;↵
for (auto &i : left)↵
st.insert(i);↵
for (auto &i : left)↵
{↵
for (ll j = 1; j <= n; j++)↵
{↵
if (((og[i][j] == 1) && (adj[i][j] == 0)) && (st.find(j) == st.end()))↵
{↵
cout << i << " " << j << "\n";↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
recommended reading material: https://cses.fi/book/book.pdf#page=197↵
I have implemented this article in the above code↵
</spoiler>↵
↵
↵
<spoiler summary="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
{↵
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";
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 0; i <= n; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis, n))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)↵
{↵
visited[node] = 1;↵
left.push_back(node);↵
for (ll i = 0; i <= n; i++)↵
{↵
if (visited[i])↵
continue;↵
// if (og[node][i] == -1)↵
// continue;↵
// if (og[node][i] == 0)↵
// continue;↵
if (og[node][i] <= 0)↵
continue;↵
dfs2(i, og, left, visited, n);↵
}↵
}↵
int main()↵
{↵
fastio;↵
ll n, m, k;↵
cin >> n >> m >> k;↵
vector<vector<ll>> adj(n + m + 2, vector<ll>(n + m + 2, -1));↵
vector<vector<ll>> og(n + m + 2, vector<ll>(n + m + 2, -1));↵
ll sum = 0;↵
for (ll i = 0; i < k; i++)↵
{↵
ll x, y;↵
ll w = 1;↵
cin >> x >> y;↵
y += n;↵
// y += 500;↵
og[x][y] = w;↵
// og[y][x] = w;↵
// og[y][x] = w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
// adj[y][x] = 0;↵
}↵
adj[x][y] = w;↵
adj[y][x] = 0;↵
sum += w;↵
}↵
for (ll i = 1; i <= n; i++)↵
{↵
adj[0][i] = 1;↵
og[0][i] = 1;↵
}↵
for (ll i = n + 1; i <= n + m; i++)↵
{↵
adj[i][n + m + 1] = 1;↵
og[i][n + m + 1] = 1;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + m + 2, 0);↵
bool f = dfs(0, n + m + 1, adj, path, sum, vis, n + m + 1);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll z = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
// for (ll i = 0; i <= n + m + 1; i++)↵
// {↵
// for (ll j = 0; j <= n + m + 1; j++)↵
// {↵
// cout << adj[i][j] << " ";↵
// }↵
// cout << "\n";↵
// }↵
cout << ans << "\n";↵
vector<ll> left;↵
// vector<ll> visited(n + m + 2, 0);↵
// dfs2(0, adj, left, visited, n + m + 1);↵
for (ll i = 1; i <= n; i++)↵
{↵
left.push_back(i);↵
}↵
unordered_set<ll> st;↵
for (auto &i : left)↵
{↵
st.insert(i);↵
}↵
for (auto &i : left)↵
{↵
for (ll j = n + 1; j <= n + m; j++)↵
{↵
if (((og[i][j] == 1) && (adj[i][j] == 0)))↵
{↵
cout << i << " " << j - n << "\n";↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Thinking">↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
read this: https://cses.fi/book/book.pdf#page=196↵
this article helps you to find the length of the path↵
now to find the path.. we do this:↵
start from vertex 1↵
go through all the edges,.. and check if there is an edge,.. whose reverse edge(that we artificially create in ford fulkerson algorithm) has a value,.. and this edge has value 0↵
this means that this edge is included in the max flow path↵
we coninue this till we reach the end↵
finally we print the answer.↵
We maintain a set of pairs to make sure we don't consider an edge twice↵
</spoiler>↵
↵
↵
<spoiler summary="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 dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)↵
{↵
vis[node] = 1;↵
if (node == dest)↵
{↵
path.push_back(node);↵
return true;↵
}↵
for (ll i = 1; i <= n; i++)↵
{↵
if (adj[node][i] == -1)↵
continue;↵
if (vis[i])↵
continue;↵
if (adj[node][i] < threshhold)↵
{↵
continue;↵
}↵
if (dfs(i, dest, adj, path, threshhold, vis, n))↵
{↵
path.push_back(node);↵
return true;↵
}↵
}↵
return false;↵
}↵
// void dfs2(ll node, vector<vector<ll>> &adj, vector<vector<ll>> &og, ll n, set<pair<ll, ll>> &st)↵
// {↵
// if (node != n)↵
// cout << node << " ";↵
// else if (node == n)↵
// cout << node << "\n";↵
// for (ll i = 1; i <= n; i++)↵
// {↵
// if (((adj[node][i] == 0) && (og[node][i] == 1)) && (st.find({node, i}) == st.end()))↵
// {↵
// st.insert({node, i});↵
// dfs2(i, adj, og, n, st);↵
// }↵
// }↵
// }↵
// bool dfs2(ll node, ll n, vector<vector<ll>> &adj, vector<vector<ll>> &og, vector<vector<ll>> &paths)↵
// {↵
// for (ll i = 1; i <= n; i++)↵
// {↵
// if ((adj[node][i] == 0) && (og[node][i] == 1))↵
// {↵
↵
// }↵
// }↵
// }↵
int main()↵
{↵
fastio;↵
ll n, m;↵
cin >> n >> m;↵
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));↵
vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));↵
ll sum = 0;↵
for (ll i = 0; i < m; i++)↵
{↵
ll x, y;↵
ll w = 1;↵
cin >> x >> y;↵
og[x][y] = w;↵
if (adj[x][y] == -1)↵
{↵
adj[x][y] = 0;↵
}↵
adj[x][y] = w;↵
if (adj[y][x] == -1)↵
adj[y][x] = 0;↵
sum += w;↵
}↵
ll ans = 0;↵
while (sum > 0)↵
{↵
vector<ll> path;↵
vector<ll> vis(n + 1, 0);↵
bool f = dfs(1, n, adj, path, sum, vis, n);↵
if (f == true)↵
{↵
reverse(path.begin(), path.end());↵
ll z = path.size();↵
ll minedgewt = LLONG_MAX;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);↵
}↵
ans += minedgewt;↵
for (ll i = 0; i < z - 1; i++)↵
{↵
adj[path[i]][path[i + 1]] -= minedgewt;↵
adj[path[i + 1]][path[i]] += minedgewt;↵
}↵
}↵
else↵
sum /= 2;↵
}↵
cout << ans << "\n";↵
set<pair<ll, ll>> ed;↵
// unordered_set<ll> ed;↵
for (ll i = 0; i < ans; i++)↵
{↵
vector<ll> v = {1};↵
int x = 1;↵
while (x != n)↵
{↵
for (ll i = 1; i <= n; i++)↵
{↵
if (((adj[x][i] == 0) && (og[x][i] == 1)) && (ed.find({x, i}) == ed.end()))↵
{↵
v.push_back(i);↵
ed.insert({x, i});↵
x = i;↵
break;↵
}↵
}↵
}↵
cout << v.size() << "\n";↵
for (auto i : v)↵
cout << (i) << " ";↵
cout << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
I hope that you will find these helpful, and will also find it in your hearts to forgive any mistake which might have crept in unknowingly. Also, any feedback is welcome.↵
↵
Peace!!
