10305 - Ordering Tasks
Moderator: Board moderators
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
thnx darko. i did wrong method.
now i changed my method & follow --"i must be executed before task j"!!!
so!!!!:(
more I/O.
12 7
1 3
3 8
3 4
4 12
4 7
7 11
7 10
output:
1 2 5 6 9 3 4 7 10 11 12 8
12 10
1 3
3 8
3 4
8 12
4 7
7 11
7 10
3 2
4 5
12 9
output:
1 6 3 2 4 5 7 10 11 8 12 9
5 4
1 2
2 3
1 3
1 5
output:
1 4 2 3 5
so correct??
now i changed my method & follow --"i must be executed before task j"!!!
so!!!!:(
more I/O.
12 7
1 3
3 8
3 4
4 12
4 7
7 11
7 10
output:
1 2 5 6 9 3 4 7 10 11 12 8
12 10
1 3
3 8
3 4
8 12
4 7
7 11
7 10
3 2
4 5
12 9
output:
1 6 3 2 4 5 7 10 11 8 12 9
5 4
1 2
2 3
1 3
1 5
output:
1 4 2 3 5
so correct??
Your output looks OK to me, what method are you using?
Btw, for that input
I got this:
Btw, for that input
Code: Select all
12 7
1 3
3 8
3 4
4 12
4 7
7 11
7 10
12 10
1 3
3 8
3 4
8 12
4 7
7 11
7 10
3 2
4 5
12 9
5 4
1 2
2 3
1 3
1 5
0 0
Code: Select all
1 3 4 7 12 11 10 9 8 6 5 2
1 3 4 8 7 12 11 10 9 6 5 2
1 2 5 4 3
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
i just used DFS.
sorry for being late reply.
here is my code. plz help me to get accepted.![:)](./images/smilies/icon_smile.gif)
sorry for being late reply.
here is my code. plz help me to get accepted.
![:)](./images/smilies/icon_smile.gif)
Code: Select all
code removed
Last edited by asif_rahman0 on Tue May 09, 2006 12:09 pm, edited 1 time in total.
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
-
- New poster
- Posts: 19
- Joined: Wed Jan 11, 2006 9:57 am
- Location: Dhaka
10305(Ordering Tasks) WA makes me mad
I don't know why this type of normal topological sort gives me WA after .002 secs for 5 times. If the algo is right there is not even any necessity to check several inputs. But I tried all the inputs posted before but could not find out the bug.
Now plssssssssssssss check my code and help me.
........................................................................................................
code deleted after ACC
Thanks DP.It was an initialization error.
Now plssssssssssssss check my code and help me.
........................................................................................................
code deleted after ACC
Thanks DP.It was an initialization error.
Last edited by Shuvra(CSE-BUET) on Thu Aug 17, 2006 7:10 pm, edited 1 time in total.
Life is a challenge.
10305 ordering tasks (plz plz help)
plz help me , im getting RA .can u plz tell me where im wrong.
im posting my code ..
im posting my code ..
Code: Select all
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class acm
{
public:
int xxx()
{
vector< vector<int> > a;
int n1,n2,first=0,last=0,co=0,count=0,count1=0,co1=0;
vector<int> v,ans;
cin>>n1>>n2;
while(n1!=0 || n2!=0)
{
v.push_back(n1);
v.push_back(n2);
a.push_back(v);
v.clear();
cin>>n1>>n2;
}
for(int i=1;i<=a[0][1];i++)
{
for(int j=1;j<=a[0][1];j++)
{
if(a[i][0]==a[j][1])
count++;
}
if(count==0)
{
ans.push_back(a[i][0]);
break;
}
}
for(int j=1;j<=a[0][1];j++)
{
for(int i=0;i<ans.size();i++)
{
if(a[j][0]==ans[i] )
first=1;
if(a[j][1]==ans[i])
last=1;
}
if(first!=1 && last!=1)
{
ans.push_back(a[j][0]);
ans.push_back(a[j][1]);
first=0;
last=0;
}
if(first==1 && last !=1)
{
ans.push_back(a[j][1]);
first=0;
last=0;
}
if(first!=1 && last==1)
{
for(int tt=0;tt<ans.size();tt++)
{
if(a[j][1]==ans[tt])
co1++;
break;
}
ans.insert(ans.begin()+co1,a[j][0]);
}
if(first==1 && last ==1)
{
first=0;
last=0;
co=0;
for(int k=0;k<ans.size();k++)
{
if(ans[k]!=a[j][1])
{
co++;
}
if(ans[k]==a[j][1])
break;
}
for(int t=0;t<co;t++)
{
if(ans[t]==a[j][0])
{
count1=1;
}
}
if(count1!=1)
{
for(int r=0;r<ans.size();r++)
{
if(ans[r]==a[j][0])
{
ans.erase(ans.begin()+r);
ans.insert(ans.begin()+co,a[j][0]);
break;
}
}
}
}
}
for(int i=1;i<=a[0][0];i++)
{
for(int j=0;j<ans.size();j++)
{
if(i==ans[j])
co++;
}
if(co==0)
{
ans.push_back(i);
}
else
co=0;
}
for(int i=0;i<ans.size();i++)
{
cout<<ans[i]<<" ";
}
return 0;
}
};
int main()
{
class acm x;
x.xxx();
}
-
- New poster
- Posts: 3
- Joined: Thu Jul 20, 2006 11:40 am
WA
Hi, noob's passing by. I tried this problem but I got a WA during 0.000 seconds. I have checked my program with the input above, and I find them logically correct. I do not know what's wrong, so I hope you guys can give me any hints on what I have done wrong.
Btw, I'm using a basic algorithm of in-degree counting.
The following are the inputs and their respective outputs:
Thanks in advance.
Btw, I'm using a basic algorithm of in-degree counting.
Code: Select all
Code Removed.
Code: Select all
12 7
1 3
3 8
3 4
4 12
4 7
7 11
7 10
Output: 1 2 5 6 9 3 4 8 7 12 10 11
12 10
1 3
3 8
3 4
8 12
4 7
7 11
7 10
3 2
4 5
12 9
Output: 1 6 3 2 4 8 5 7 12 9 10 11
5 4
1 2
2 3
1 3
1 5
Output: 1 4 2 5 3
Life is a sine wave where there are many ups and downs.
-
- New poster
- Posts: 3
- Joined: Thu Jul 20, 2006 11:40 am
WHY 10305 - Ordering Tasks WA
ok code results everything okay
but WA why
but WA why
Code: Select all
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define S 222
#define INF 9999
vector<int> adj[S];
enum{White=0, Gray, Black,NO};
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,less<PII> > P;
int color[S];
int A[S];
int pre[S];
int d[S];
int F[S];
int N,M,tme;
void initialize()
{
int i,j;
for(i=0; i<S; i++)
{
F[i]=0; pre[i]=-1;d[i]=INF;
adj[i].clear();color[i]=NO;
for(j=0; j<S; j++){}
}
}
void DFS(int u)
{
color[u]=Gray;
tme++;
d[u]=tme;
for(int i=0; i< adj[u].size(); i++)
{
int v=adj[u][i];
if(color[v]==White)
{
pre[v]=u;
DFS(v);
}
}
color[u]=Black;
tme=tme+1;
F[u]=tme;
}
int main()
{
int u,v,s,t;
int i,j,k,l;
while(scanf("%d%d",&N,&M)==2&&N&&M)
{
initialize();
for(i=0; i<M; i++)
{
scanf("%d%d",&u,&v);
adj[u].push_back(v);
color[u]=color[v]=White;
}
tme=0;
for(i=1; i<=N; i++)
{
if(color[i]==White)
{
DFS(i);
}
}
//cout << "Node\tDiscovery\tfinishing\n";
for(i=1; i<=N; i++)
{
//cout << i<<"\t"<<d[i]<<"\t\t"<<F[i]<<endl;
P.push(make_pair(F[i],i));
}
while(!P.empty())
{
int n=P.top().second;
int f=P.top().first;
P.pop();
cout << n<<" ";//<<f<<endl;
}
cout << endl;
}
return 0;
}
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
How i get Acc
it`s really strange , for this problem we should use topological sort and dfs but i get Acc with this code
please anybody reply me why I get acc ,
i think this method is wrong ,(maybe inputs aren`t challengeable)
do u agree with me ???
![:o](./images/smilies/icon_eek.gif)
Code: Select all
struct d{
int x;double t;
}list[101];
int main(){
//ifstream cin("c.in");
int n,m;
while(cin>>n>>m&&!(!n&&!m)){
int x,y;
for(int i=0;i<=n;i++) list[i].x=i,list[i].t=0;
for(int i=0;i<m;i++) cin>>x>>y,list[x].t-=1.0,list[y].t+=1.5;
for(int i=1;i<=n;i++){// sorting
for(int j=i+1;j<=n;j++){
if(list[i].t>list[j].t){
swap(list[i].t,list[j].t);
swap(list[i].x,list[j].x);
}
}
}
for(int i=1;i<n;i++) cout<<list[i].x<<" ";
cout<<list[n].x<<endl;
}
}
i think this method is wrong ,(maybe inputs aren`t challengeable)
do u agree with me ???
Impossible says I`m possible
-
- New poster
- Posts: 1
- Joined: Wed Aug 12, 2009 10:57 pm
Runtime Error with 10305(Ordering Tasks) plzz help
i get RE error each time i submit
please anyone tell me what might the reason be?
any help would be appreciated..
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
please anyone tell me what might the reason be?
![:roll:](./images/smilies/icon_rolleyes.gif)
![:roll:](./images/smilies/icon_rolleyes.gif)
![:roll:](./images/smilies/icon_rolleyes.gif)
any help would be appreciated..
Code: Select all
removed after AC
Last edited by Yuna Reichmann on Sat Aug 22, 2009 8:08 pm, edited 2 times in total.
![Image](http://img39.imageshack.us/img39/4023/wonderfullife2009021021.jpg)
Re: 10305 - Ordering Tasks
hi,,,
what wrong with this
gave me run time error every time i submit it
help,,
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
void logic (vector<vector <int> > graph)
{
vector<int> ret;
vector<int> indgree(graph.size(),0);
queue<int> q;
for(int i=0;i<graph.size();i++)
for(int j=0;j<graph.size();i++)
indgree[graph[j]] ++;
for(int i=0;i<graph.size();i++)
if(!indgree) q.push(i);
while(! q.empty())
{
int res=q.front();
q.pop();
ret.push_back(res);
for(int i=0;i<graph[res].size();i++)
{
indgree[graph[res]]--;
if(! indgree[graph[res]]) q.push(graph[res]);
}
}
if(ret.size()!=graph.size())
ret.clear();
for(int i=1;i<graph.size();i++)
cout<<ret<<" ";
}
int main()
{
//freopen("in.txt","rt",stdin);
//freopen("out.txt","wt",stdout);
int n,m;
cin>>n>>m;
int nn=n;
vector<int> res(n);
vector<vector <int> > graph(n+1);
while(nn>0)
{
cin>>n>>m;
if(n==0&&m==0) break;
graph[n].push_back(m);
nn--;
}
logic(graph);
return 0;
}
what wrong with this
gave me run time error every time i submit it
help,,
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
void logic (vector<vector <int> > graph)
{
vector<int> ret;
vector<int> indgree(graph.size(),0);
queue<int> q;
for(int i=0;i<graph.size();i++)
for(int j=0;j<graph.size();i++)
indgree[graph[j]] ++;
for(int i=0;i<graph.size();i++)
if(!indgree) q.push(i);
while(! q.empty())
{
int res=q.front();
q.pop();
ret.push_back(res);
for(int i=0;i<graph[res].size();i++)
{
indgree[graph[res]]--;
if(! indgree[graph[res]]) q.push(graph[res]);
}
}
if(ret.size()!=graph.size())
ret.clear();
for(int i=1;i<graph.size();i++)
cout<<ret<<" ";
}
int main()
{
//freopen("in.txt","rt",stdin);
//freopen("out.txt","wt",stdout);
int n,m;
cin>>n>>m;
int nn=n;
vector<int> res(n);
vector<vector <int> > graph(n+1);
while(nn>0)
{
cin>>n>>m;
if(n==0&&m==0) break;
graph[n].push_back(m);
nn--;
}
logic(graph);
return 0;
}