Why care about cycles?

maybe more than one component!

How we can solve this using flow? Some hints?
Thanks,
Ostap

axper jan..
good that found ...
can you send message? vk com/mikaelarakelyan
....
sometimes an idea is bad for a solution

Great hint!!!

3ks!!

I suppose that's because server use JDK1.5, not 1.6

Maybe their method of calculating Running time is different

Is it  special judge?

I had a trap for that, it didn't signal. So, they ARE ascending.

If your greed is chain-based, then it's correct

Edited by author 01.08.2008 14:40

(Can there exist more than 2 doors between rooms?)

No because numbers of adjacent rooms are ASCENDING.

Yes, of course

Solution is O(M), M - number of doors

#include<iostream.h>
const int max = 101;
int ke[max][max],color[max][max],mau[max][3];
int n;
int fillchar(int mas[max][max],int rosme=max,int k = 0)
{
int j;
for(int i = 1; i<rosme;i++)
{for(j = 1; j<rosme;j++) mas[i][j] = k;}

return 1;
}

int fillchar1(int mas[max][3],int rosme=3,int k = 0)
{
int j;
for(int i = 1; i<rosme;i++)
{for(j = 1; j<rosme;j++) mas[i][j] = k;}

return 1;
}
//------------------------------------------------------------------------
void input()
{
int i,j;
cin>>n;
for (i = 1;i<=n;i++)
{cin>>ke[i][0];
for(j=1;j<=ke[i][0];j++)
{cin>>ke[i][j]; }
}
}
//-----------------------------------------------------------------------
void chonmau(int i,int &t)
{
if (mau[i][1]>=mau[i][2])
t = 2; else t = 1;
}
//---------------------------------------------------------------------
void tomau(int i,int j,int t)
{int flag = 0;
int u,v;
do
{
color[i][j] = t;
mau[i][t] = mau[i][t] + 1;
u = ke[i][j];
flag = 0;
for (v = 1; v<=ke[u][0]; v++)
if(ke[u][v] == i ) { flag =1; break;}


color[u][v] = 3-t;
mau[u][3-t] = mau[u][3-t] +1;
flag = 0;
for (v = 1;v<=ke[u][0];v++) if (color [u][v] == 0) {flag = 1;break;}

i = u; j = v;
} while (color[i][j] != 0);

}
//------------------------------------------------------------------
void solve()
{ int i,j,t;
fillchar(color);
fillchar1(mau);

for (i = 1;i<=n;i++)
{for(j = 1;j<=ke[i][0];j++)
if (color[i][j] == 0)
{
chonmau(i,t);

tomau(i,j,t);

}
}
}
//--------------------------------------------------------------------------
void out()
{ int i,j;
for (i=1;i<=n;i++)
{for(j=1;j<=ke[i][0];j++)
switch(color[i][j])
{
case 1:cout<<"G ";break;
case 2:cout<<"Y ";break;
}

cout<<endl;
}

}
void main()
{
input();
solve();
out();
}
i fink soo, but she dont work

Edited by author 09.07.2007 21:51

Edited by author 09.07.2007 22:03

#include<iostream.h>
const int max = 101;
int ke[max][max],color[max][max],mau[max][3];
int n;
int fillchar(int mas[max][max],int rosme=max,int k = 0)
{
int j;
for(int i = 1; i<rosme;i++)
{for(j = 1; j<rosme;j++) mas[i][j] = k;}

return 1;
}

int fillchar1(int mas[max][3],int rosme=3,int k = 0)
{
int j;
for(int i = 1; i<rosme;i++)
{for(j = 1; j<rosme;j++) mas[i][j] = k;}

return 1;
}
//------------------------------------------------------------------------
void input()
{
int i,j;
cin>>n;
for (i = 1;i<=n;i++)
{cin>>ke[i][0];
for(j=1;j<=ke[i][0];j++)
{cin>>ke[i][j]; }
}
}
//-----------------------------------------------------------------------
void chonmau(int i,int &t)
{
if (mau[i][1]>=mau[i][2])
t = 2; else t = 1;
}
//---------------------------------------------------------------------
void tomau(int i,int j,int t)
{int flag = 0;
int u,v;
do
{
color[i][j] = t;
mau[i][t] = mau[i][t] + 1;
u = ke[i][j];
flag = 0;
for (v = 1; v<=ke[u][0]; v++)
if(ke[u][v] == i ) { flag =1; break;}


color[u][v] = 3-t;
mau[u][3-t] = mau[u][3-t] +1;
flag = 0;
for (v = 1;v<=ke[u][0];v++) if (color [u][v] == 0) {flag = 1;break;}

i = u; j = v;
} while (color[i][j] == 0);

}
//------------------------------------------------------------------
void solve()
{ int i,j,t;
fillchar(color);
fillchar1(mau);

for (i = 1;i<=n;i++)
{for(j = 1;j<=ke[i][0];j++)
if (color[i][j] == 0)
{
chonmau(i,t);

tomau(i,j,t);

}
}
}
//--------------------------------------------------------------------------
void out()
{ int i,j;
for (i=1;i<=n;i++)
{for(j=1;j<=ke[i][0];j++)
switch(color[i][j])
{
case 1:cout<<"G ";break;
case 2:cout<<"Y ";break;
}

cout<<endl;
}

}
void main()
{
input();
solve();
out();
}