DELETED
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 158 |
6 | -is-this-fft- | 157 |
7 | awoo | 156 |
8 | djm03178 | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
DELETED
Hey guys...
Recently I was solving this problem from CSES.
Here is what I have tried...
Firsly ,
now ready to answer queries.
if given starting node is involved any cycle then ending node should also be in same cycle. otherwise ans is -1.
If both are in same cycle then we can compute distance between them in O(1) using node nos. of both node.
Now , if Starting node is not in any cycle.
Then ending node must be ancestor of it otherwise ans is -1 (not reachable) Now as ending node is ancestor of starting node (talking in inverted tree) , we can walk upto that node and compute desired no. of jumps. It will be in O(logn).
By implementing this idea , I am getting WA in one TC ( Out of 11 ).
You can find my code here.
#include<bits/stdc++.h>
#define maxn 300005
#define ll long long int
using namespace std;
// https://cses.fi/problemset/task/1160/
set<int> par[maxn];
vector<int> nxt(maxn);
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);
vector<bool> v1(maxn,false),v2(maxn,false);
vector<vector<int>> cycle;
vector<int> tmp;
int cyc_id=0;
int nn=0;
int start=-1;
vector<int> tin(maxn),tout(maxn);
int tem=0;
vector<int> latkav;
void dfs(int n)
{
v1[n]=true;
int c=nxt[n];
if(v1[c] && !v2[c])
{
nxt[n]=-1;
par[c].erase(n);
latkav.push_back(n);
start=c;
}
if(!v1[c]) dfs(c);
if(start!=-1)
{
tmp.push_back(n);
kai_cyc[n]=cyc_id;
kyo_node[n]=nn++;
if(n==start)
{
cycle.push_back(tmp);
start=-1;
tmp.clear();
nn=0;
cyc_id++;
}
}
v2[n]=true;
}
vector<vector<int>> up;
int mxh;
void dfs1(int n,int p)
{
tin[n]=tem++;
up[n][0]=p;
for(int i=1;i<=mxh;i++)
{
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }
}
for(int c:par[n]) dfs1(c,n);
tout[n]=tem++;
}
bool isanc(int u,int v)
{
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
int main()
{
jaldi
int n,q;
cin>>n>>q;
for(int i=1,x;i<=n;i++)
{
cin>>x;
nxt[i]=x;
par[x].insert(i);
}
for(int i=1;i<=n;i++)
{
if(!v1[i]) dfs(i);
}
//for(vector<int> v:cycle) { deb(v); } //if in same cycle then o(1) ans, else binary lifting
mxh=ceil(log2(n));
up.assign(n+1,vector<int>(mxh+1,-1));
for(int x:latkav) dfs1(x,-1);
while(q--)
{
int start,end;
cin>>start>>end;
if(start==end) { cout<<"0\n"; continue; }
if(kai_cyc[start]!=-1)
{
if(kai_cyc[start]==kai_cyc[end])
{
int s=kyo_node[start];
int e=kyo_node[end];
int sz=cycle[kai_cyc[start]].size();
cout<<(s-e+sz)%sz<<"\n";
}
else { cout<<"-1\n"; }
continue;
}
if(isanc(end,start))
{
int jump=0;
for(int i=mxh;i>=0;i--)
{
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }
}
cout<<jump+1<<"\n";
}
else { cout<<"-1\n"; }
}
return 0;
}
So , can someone point out what am I doing wrong or any cases that I am missing.
Thanks in advance :)
UPD
As pwild sir pointed out , I was missing that cases.
To overcome that , I just added small logic to my code and it got ACCEPTED.
If you want to see code...
#include<bits/stdc++.h>
#define maxn 200005
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// https://cses.fi/problemset/task/1160/
set<int> par[maxn];
vector<int> nxt(maxn);
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);
vector<bool> v1(maxn,false),v2(maxn,false);
vector<vector<int>> cycle;
vector<int> tmp;
int cyc_id=0;
int nn=0;
int start=-1;
vector<int> tin(maxn),tout(maxn);
int tem=0;
vector<int> latkav;
void dfs(int n)
{
v1[n]=true;
int c=nxt[n];
if(v1[c] && !v2[c])
{
par[c].erase(n);
latkav.push_back(n);
start=c;
}
if(!v1[c]) dfs(c);
if(start!=-1)
{
tmp.push_back(n);
kai_cyc[n]=cyc_id;
kyo_node[n]=nn++;
if(n==start)
{
cycle.push_back(tmp);
start=-1;
tmp.clear();
nn=0;
cyc_id++;
}
}
v2[n]=true;
}
vector<vector<int>> up;
int mxh;
void dfs1(int n,int p)
{
tin[n]=tem++;
up[n][0]=p;
for(int i=1;i<=mxh;i++)
{
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }
}
for(int c:par[n]) dfs1(c,n);
tout[n]=tem++;
}
bool isanc(int u,int v)
{
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
int main()
{
fastio
int n,q;
cin>>n>>q;
for(int i=1,x;i<=n;i++)
{
cin>>x;
nxt[i]=x;
par[x].insert(i);
}
for(int i=1;i<=n;i++)
{
if(!v1[i]) dfs(i);
}
mxh=ceil(log2(n));
up.assign(n+1,vector<int>(mxh+1,-1));
for(int x:latkav) dfs1(x,-1);
while(q--)
{
int start,end;
cin>>start>>end;
if(start==end) { cout<<"0\n"; continue; }
if(kai_cyc[start]!=-1)
{
if(kai_cyc[start]==kai_cyc[end])
{
int s=kyo_node[start];
int e=kyo_node[end];
int sz=cycle[kai_cyc[start]].size();
cout<<(s-e+sz)%sz<<"\n";
}
else { cout<<"-1\n"; }
continue;
}
if(isanc(end,start))
{
int jump=0;
for(int i=mxh;i>=0;i--)
{
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }
}
cout<<jump+1<<"\n";
}
else
{
int jump=0;
for(int i=mxh;i>=0;i--)
{
if(up[start][i]!=-1) { start=up[start][i]; jump+=1<<i;}
}
if(kai_cyc[start]==kai_cyc[end])
{
int s=kyo_node[start];
int e=kyo_node[end];
int sz=cycle[kai_cyc[start]].size();
cout<<((s-e+sz)%sz+jump)<<"\n";
}
else { cout<<"-1\n"; }
}
}
return 0;
}
Hello guys , I am having trouble solving this problem
You can read problem statement here also.
You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).
Your task is to process q queries of the form: when you begin on planet x and travel through k teleporters, which planet will you reach?
n , q can be upto 2.10^5.
k can be upto 10^9.
So , any hint to solve this problem will be grateful.
Thanks in advance :)
Hello everyone...
First of all sorry but I am writing the blog on same doubt again because there was some issues with code in last blog.
So , recently I was solving this problem ...
You are given a directed weighted graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle.
I am aware of solving this problem using Bellman Ford's Algorithm , But I am trying another approach which is giving me WA in 1 Test Case (total 13 is there) .
So , Can anyone point out whether this approach is correct or not ... and If it is correct then suggest me some modification else give some counter examples where this code might fail.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define mod 1000000007
#define check exit(0)
#define nl cout<<endl;
#define inp 30000
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; }
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace __gnu_pbds;
using namespace std;
vector<pair<ll,ll>> g[inp];
vector<ll> weight(inp,0);
vector<bool> vis1(inp,false),vis2(inp,false);
vector<ll> par(inp);
vector<ll> ans;
void dfs(ll n,ll tot)
{
vis1[n]=true;
weight[n]=tot;
for(pair<ll,ll> c:g[n])
{
if(vis1[c.first] && !vis2[c.first]) // cycle detected
{
ll tmp = weight[n]-weight[c.first] + c.second; //weight of cycle
if(tmp<0)
{
ans.push_back(c.first);
while(n!=c.first)
{
ans.push_back(n);
n=par[n];
}
ans.push_back(c.first);
reverse(ans.begin(),ans.end());
cout<<"YES\n";
for(int x:ans) cout<<x<<" ";
check;
}
}
if(!vis1[c.first]) { par[c.first]=n; dfs(c.first , tot+c.second); }
}
vis2[n]=true; //completely explored node
}
int main()
{
jaldi
ll n,m; //vertices & edges
cin>>n>>m;
vector<vector<ll>> arr(n+1,vector<ll>(n+1,LLONG_MAX)); // adj. matrix so that we can select edge with
// minimum weight
for(ll i=1,u,v,w;i<=m;i++)
{
cin>>u>>v>>w;
arr[u][v]=min(arr[u][v],w);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(arr[i][j]<LLONG_MAX) { g[i].push_back({j,arr[i][j]}); } //preparing adj. list
}
}
for(int i=1;i<=n;i++)
{
if(!vis1[i])
{
dfs(i,0);
}
}
cout<<"NO\n"; //Neg. cycle not found
return 0;
}
Any kind of help will be appreciated.
**Feel free to downvote but help me if you know the answer ;) **
THANKS.
Hello Everyone ...
Today I was solving this problem ... Problem statement : You are given a directed weighted graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle.
I am aware of solving this problem using Bellman Ford's Algorithm , But I am trying another approach which is giving me WA in 1 Test Case (total 13 is there) .
So , Can anyone point out whether this approach is correct or not ... and If it is correct then suggest me some modification otherwise give some counter examples where this code might fail.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define mod 1000000007
#define check exit(0)
#define nl cout<<endl;
#define inp 30000
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; }
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace __gnu_pbds;
using namespace std;
vector<ll> weight(inp,0);
vector<pair<ll,ll>> g[inp];
vector<bool> vis1(inp,false),vis2(inp,false);
vector<ll> par(inp);
vector<ll> ans;
void dfs(ll n,ll tot)
{
vis1[n]=true;
weight[n]=tot;
for(pair<ll,ll> c:g[n])
{
if(vis1[c.first] && !vis2[c.first]) // cycle detected
{
ll tmp = weight[n]-weight[c.first] + c.second;
if(tmp<0)
{
ans.push_back(c.first);
while(n!=c.first)
{
ans.push_back(n);
n=par[n];
}
ans.push_back(c.first);
reverse(ans.begin(),ans.end());
cout<<"YES\n";
deb(ans);
check;
}
}
if(!vis1[c.first]) { par[c.first]=n; dfs(c.first , tot+c.second); }
}
vis2[n]=true;
}
int main()
{
jaldi
ll n,m;
cin>>n>>m;
vector<vector<ll>> arr(n+1,vector<ll>(n+1,LLONG_MAX));
for(ll i=1,u,v,w;i<=m;i++)
{
cin>>u>>v>>w;
arr[u][v]=min(arr[u][v],w);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(arr[i][j]<LLONG_MAX) { g[i].push_back({j,arr[i][j]}); }
}
}
for(int i=1;i<=n;i++)
{
if(!vis1[i])
{
dfs(i,0);
}
}
cout<<"NO\n";
return 0;
}
Thanks in advance :) and sorry for my bad english.
Hey there ...
Today I was solving these problem click ... and I got tle verdict on TC 5. Here's a link to my solution click.
As much as I got , time complexity of my above solution is O(nlogn) where n can be upto 10^5.
So , I am not getting why it is giving tle verdict. So any help regarding this would be appreciated.
Thanks in advance ;)
UPD ==================: Was getting TLE due to ( endl ).
Can someone share some problems on Articulation Points and bridges in a graph ! Thanks in advance :)
Name |
---|