Next time post in the existing thread.
Read this thread.
11060 - Beverages
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11060 - Beverages
Check input and AC output for thousands of problems on uDebug!
Re: 11060 - Beverages
can anyone help me to find my problem?I used a toposort.
thanks in advance.
thanks in advance.
Code: Select all
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define FRU freopen("out.txt","w",stdout)
#define FRO freopen("in.txt","r",stdin)
#define pb push_back
//const int row[]={-1, -1, -1, 0, 0, 1, 1, 1}; // Kings Move
//const int col[]={-1, 0, 1, -1, 1, -1, 0, 1}; // Kings Move
//const int row[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int col[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
//const int row[]={-1,0,0,1,0};
//const int col[]={0,-1,1,0,0};
using namespace std;
vector<string> modd,ans;
map<string,int>mmp;
vector<int>edge[1001],ans1;
bool vis[1001];
map<int,string>mmp1;
int blah,cnt;
void dfs(int sou)
{
vis[sou]=1;
cnt++;
for(int i=0; i<edge[sou].size(); i++)
{
int v=edge[sou][i];
if(vis[v]==0)dfs(v);
}
ans1.pb(sou);
}
int main()
{
//FRO;
//FRU;
//std::ios_base::sync_with_stdio(false);
int a,b,c,i,j,k,tc,t=0;
int n,m,cnt=0;
string s,s1,s2;
while(scanf("%d",&n)!=EOF)
{
if(t!=0)printf("\n");
for(i=0;i<101;i++)edge[i].clear();
modd.clear();
ans.clear();
mmp1.clear();
mmp.clear();
ans1.clear();
for(i=0; i<n; i++)
{
cin>>s;
modd.pb(s);
mmp[s]=i+1;
mmp1[i+1]=s;
}
scanf("%d",&m);
for(i=0; i<m; i++)
{
cin>>s>>s1;
int tmp=mmp[s],tmp1=mmp[s1];
edge[tmp1].pb(tmp);
}
memset(vis,0,sizeof vis);
blah=0;
for(i=0; i<n; i++)
{
if(vis[i+1]==0)
{
cnt=0;
dfs(i+1);
}
}
printf("Case #%d: Dilbert should drink beverages in this order:",++t);
for(i=0; i<n; i++)cout<<" "<<mmp1[ans1[i]];
printf(".\n");
}
return 0;
}
Re: 11060 - Beverages
Your output doesn't match 3rd case. Read this thread
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 11060 - Beverages
That's a pretty cool but obscure problem. 
If you don't understand the mystic "In the case there is no relation between two beverages" part, check lighted's answer on page 5 here, it explains what you have to do. It's a simple topological sort problem in fact.
The statement should be better explain, I spent far too much time on this one compared to its real difficulty.

If you don't understand the mystic "In the case there is no relation between two beverages" part, check lighted's answer on page 5 here, it explains what you have to do. It's a simple topological sort problem in fact.
The statement should be better explain, I spent far too much time on this one compared to its real difficulty.

Re: 11060 - Beverages
wrong output for the third sample case
Note: I'm changing the strings with numbers starting from 0 then I'm doing normal dfs. so the case of not being relations between drinks are handled

Note: I'm changing the strings with numbers starting from 0 then I'm doing normal dfs. so the case of not being relations between drinks are handled

Code: Select all
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<set>
#include<list>
#include<climits>
#include<bitset>
#include<iterator>
#include<string.h>
#include<time.h>
#include<stdio.h>
#include<numeric> // accumulate
using namespace std;
#define print(A) printf("%s = %d\n",#A ,A);
#define printt(A,B) printf("%s = %d | %s = %d\n",#A,A,#B,B);
#define _c cout << "---" << endl;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define mem(A,B) memset(A,B,sizeof A);
#define sz(x) (int)x.size()
typedef long long ll;
typedef long long unsigned llu;
int dx[]={0,0,1,-1,1,1,-1,-1};
int dy[]={1,-1,0,0,1,-1,1,-1};
const double pi = 2 * acos(0.0);
vector<int>adj[1001];
bool vis[500];
vector<int>v;
int id;
map<string,int>hs;
map<int,string>mm;
inline void dfs(int n){
vis[n]=1;
for(int i=0;i<sz(adj[n]);++i){
int u=adj[n][i];
if(!vis[u])
dfs(u);
}
v.push_back(n);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
// freopen("b.txt", "w", stdout);
#endif
int n;
while(scanf("%d",&n)>0){
for(int i=0;i<n;++i)
adj[i].clear(),vis[i]=0;
v.clear();
hs.clear();
mm.clear();
id=0;
vector<string>cc;
while(n--){
string s;
cin >> s;
if(hs.find(s)==hs.end()){
hs[s]=id;
mm[id++]=s;
cc.push_back(s);
}
}
int m;
scanf("%d",&m);
while(m--){
string s,r;
cin >> s >> r;
int u,v;
u=hs[s];v=hs[r];
adj[v].push_back(u);
}
for(int i=0;i<id;++i)
if(!vis[i])
dfs(i);
vector<string>r;
for(int i=0;i<id;++i)
r.push_back(mm[v[i]]);
for(int i=0;i<sz(r);++i)
cout << r[i] << " ";
puts("");
}
return 0;
}
Re: 11060 - Beverages
my code is fine, passes every test case in udebug but why getting wa here?
-
- New poster
- Posts: 7
- Joined: Fri Dec 06, 2013 3:38 pm
Re: 11060 - Beverages
Hi all
I still got runtime error and i dont know why ??
Can anyone help me ?
Code : https://www.ideone.com/dO8Km9
Thanks in advance.
I still got runtime error and i dont know why ??
Can anyone help me ?
Code : https://www.ideone.com/dO8Km9
Thanks in advance.