#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop0(i,x) for(int i=0;i<x.size();i++)
#define stlloop1(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define PI 3.14159265358979323846264338328
#define MAX 2000
using namespace std;
bool visited[MAX];
int dis[MAX];
vector<int> g[MAX];
int parent[MAX];
int edge;
map<string,int> mp1;
map<int,string> mp2;
void path_print(int src,int dst)
{
if(dst==src) return;
path_print(src,parent[dst]);
cout<<mp2[parent[dst]]<<" "<<mp2[dst]<<endl;
}
int bfs(int src,int dst)
{
dis[src]=0;
ms(visited,0);
visited[src]=1;
parent[src]=-1;
qu<int> q;
q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!visited[v])
{
parent[v]=u;
visited[v]=1;
dis[v]=dis[u]+1;
q.push(v);
}
}
}
if(visited[dst]) path_print(src,dst);
else cout<<"No route"<<endl;
}
int main()
{
CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
bool test=0;
while(cin>>edge)
{
if(test) cout<<endl;
test=1;
int c=3;
for(int i=0; i<edge; i++)
{
string from,to;
cin>>from>>to;
if(mp1[from]==0)
{
mp1[from]=c;
mp2[c]=from;
c++;
}
if(mp1[to]==0)
{
mp1[to]=c;
mp2[c]=to;
c++;
}
g[mp1[from]].push_back(mp1[to]);
g[mp1[to]].push_back(mp1[from]);
}
string src,dst;
cin>>src>>dst;
if(src==dst) cout<<src<<" "<<dst<<endl;
else if(mp1[src]==0 || mp1[dst]==0) cout<<"No route"<<endl;
else bfs(mp1[src],mp1[dst]);
loop0(i,MAX) g[i].clear();
mp1.clear();
mp2.clear();
}
return 0;
}
Category Uncategorized
UVa – 567 – Risk
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop0(i,x) for(int i=0;i<x.size();i++)
#define stlloop1(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define PI 3.14159265358979323846264338328
#define MAX 2004
using namespace std;
bool visited[MAX];
int dis[MAX];
vector<int> g[MAX];
int bfs(int src,int dst)
{
ms(dis,0);
dis[src]=0;
ms(visited,0);
visited[src]=1;
qu<int> q;
q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
if(u==dst) return dis[dst];
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!visited[v])
{
visited[v]=1;
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return -1;
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int xxx,z=0;
while(scanf("%d",&xxx)==1)
{
z++;
loop0(i,xxx)
{
int xx;
scanf("%d",&xx);
g[1].pb(xx);
g[xx].pb(1);
}
for(int i=2; i<=19; i++)
{
int x,to;
scanf("%d",&x);
loop0(j,x)
{
scanf("%d",&to);
g[i].push_back(to);
g[to].push_back(i);
}
}
int n,src,dst;
scanf("%d",&n);
printf("Test Set #%d\n",z);
loop0(i,n)
{
scanf("%d %d",&src,&dst);
printf("%2d to %2d: %d\n",src,dst,bfs(src,dst));
}
printf("\n");
loop0(i,MAX) g[i].clear();
}
return 0;
}
UVa – 336 – A node too far
In UDebug of this problem,there are one or more wrong input cases for which this code will show wrong output, but actually those input cases are invalid for this problem !! So don’t bother with the UDebug output, this code will be Accepted in UVa OJ since this code is for all valid input !! 😀
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define PI 3.14159265358979323846264338328
#define MAX 2004
using namespace std;
bool visited[MAX];
int dis[MAX];
vc <int> g[MAX];
map<ll,int> mp;
int bfs(int src,ll ttl)
{
int d=1;
dis[src]=0;
ms(visited,0);
ms(dis,0);
visited[src]=1;
queue<int> Q;
Q.push(src);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!visited[v] && dis[u]+1<=ttl)
{
dis[v]=dis[u]+1;
d++;
visited[v]=1;
Q.push(v);
}
}
}
return d;
}
int main()
{
CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int edge;
for(int j=1;;)
{
cin>>edge;
if(edge==0) break;
int c=1;
for(int i=0; i<edge; i++)
{
ll from,to;
cin>>from>>to;
if(mp[from]==0)
{
mp[from]=c;
c++;
}
if(mp[to]==0)
{
mp[to]=c;
c++;
}
g[mp[from]].push_back(mp[to]);
g[mp[to]].push_back(mp[from]);
}
ll src,ttl;
while(cin>>src>>ttl)
{
if(src==0 && ttl==0) break;
int a=c-bfs(mp[src],ttl)-1;
cout<<"Case "<<j<<": "<<a<<" nodes not reachable from node "<<src<<" with TTL = "<<ttl<<"."<<endl;
j++;
}
loop0(i,MAX) g[i].clear();
mp.clear();
}
return 0;
}
UVa – 558 -Warmholes
Problem Link: https://onlinejudge.org/external/5/558.pdf Code:
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
bool bellman_ford(int node, int edge, vector<pair<pii, int> > &adj)
{
vector<long long int> dis(node, INT_MAX);
dis[0]=0;
for(int i=0; i<node; i++)
{
for(int j=0; j<edge; j++)
{
int u=adj[j].first.first;
int v=adj[j].first.second;
int cost=adj[j].second;
if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
{
dis[v]=dis[u]+cost;
}
}
}
//Running an extra loop to find out whether the graph contains any negative cycle loop or not
bool neg_cycle=0;
for(int j=0; j<edge; j++)
{
int u=adj[j].first.first;
int v=adj[j].first.second;
int cost=adj[j].second;
if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
{
neg_cycle=1;
break;
//dis[v]=INT_MAX; //Marking the nodes which will keep decreasing infinitly due to negative weight cycle
}
}
return neg_cycle;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
cin>>t;
while(t--)
{
int node,edge;
cin>>node>>edge;
vector<pair<pii, int> > adj;
for(int i=0; i<edge; i++)
{
int from,to,w;
cin>>from>>to>>w;
adj.push_back({{from, to}, w});
}
if(bellman_ford(node, edge, adj)) cout<<"possible"<<endl;
else cout<<"not possible"<<endl;
}
return 0;
}
UVa – 10324 – Zeroes and Ones
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loopn(i,n) for(int i=1;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define loopba(i,b,a) for(int i=b;i>=a;i--)
#define REV(i,n) for(i=n; i>=0; i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 1000000
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
int a[1000005];
int main()
{
CIN;
int n,i,j,k,l,c,m=1;
string s;
while(cin>>s)
{
if(s=="\n") break;
for(i=0; i<s.size(); i++)
{
if(s[i]=='1') a[i+1]=1;
else a[i+1]=0;
}
for(i=1; i<=s.size(); i++) a[i]+=a[i-1];
cin>>n;
cout<<"Case "<<m<<":"<<endl;
for(l=0; l<n; l++)
{
cin>>i>>j;
c=0;
i++,j++;
if(i>j) swap(i,j);
if(a[j]-a[i-1]==0 || a[j]-a[i-1]==(j-i+1))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
m++;
}
return 0;
}
Fall out, Codes! 