10092 - The Problem with the Problem Setter

Moderator: Board moderators

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Contact:

Re: 10092 - The Problem with the Problem Setter

Getting W.A with run time 2.416. Is my procedure OK?

Code: Select all

``````#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

#define FOR(i,a,b)   for(int i=(a);i<(b);i++)
#define REP(i,a,b)   for(int i=(a);i<=(b);i++)
#define PB           push_back

#define sz 1040

int N,M;
int cap[sz][sz],flow[sz][sz],parent[sz],s,t;
int vd[25][sz];
int top[25];

void init_p()
{
int lim = N+M+5;
FOR(i,0,lim)parent[i]=-1;
}

//MAX-FLOW: FORD FULKERSON..RESIDUAL GRAPH
bool path()
{
int u;
queue<int> qu;
char color[sz];
init_p();
memset(color,0,sizeof(color));
color[s] = 1;
qu.push(s);
while(qu.empty()==false)
{
u = qu.front();
if(u==t)break;
qu.pop();
REP(i,0,t)
{
if(((cap[u][i]-flow[u][i]) > 0) && color[i]==0)
{
color[i] = 1;
parent[i] = u;
qu.push(i);
if(i==t)break;
}
}
}
if(color[t]==0)return false;
int now,previous;
now = t;
while(parent[now] != -1)
{
previous = parent[now];
flow[previous][now] += 1;
flow[now][previous] = -flow[previous][now];
now = previous;
}
now = t;
int ind,ins;
while(1)
{
if(parent[parent[now]]==s)
{
ind = parent[now];
ins = now;
break;
}
now = parent[now];
}
vd[ind][top[ind]++] = ins;
return true;
}

void init()
{
int lim = N+M+5;
FOR(i,0,lim)
{
FOR(j,0,lim)
{
cap[i][j] = flow[i][j] = 0;
}
}
REP(i,0,N)
{
top[i] = 0;
REP(j,0,lim)
{
vd[i][j] = 0;
}
}
}

int main()
{
//	  freopen("10092.in","r",stdin);
int capacity,l,val;
while(1)
{
scanf("%d %d",&N,&M);
if(N==0 && M==0)break;
s = capacity = 0;
init();
REP(i,1,N)
{
scanf("%d",&cap[s][i]);
cap[i][s] = cap[s][i];
capacity += cap[s][i];
}
t = N+M+1;
FOR(i,N+1,t)
{
scanf("%d",&l);
FOR(j,0,l)
{
scanf("%d",&val);
cap[val][i] = 1;
}
}
FOR(i,N+1,t)
{
cap[i][t] = 1;
}
int cnt = 0;
while(path()==true)
{
cnt++;
}
if(cnt<capacity)
{
printf("0\n");
continue;
}
printf("1\n");
int li;
REP(i,1,N)
{
li = top[i];
FOR(j,0,li)
{
if(j>0)printf(" %d",vd[i][j]-N);
else printf("%d",vd[i][j]-N);
}
printf("\n");
}
}
return 0;
}
``````

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Contact:

Re: 10092 - The Problem with the Problem Setter

Well, I found that it fails for input:

Code: Select all

``````2 2
1 1
2 1 2
1 1
``````
But still the updated version gets W.A in running time 0.176s.

Code: Select all

``````#include <cstdio>
#include <queue>

using namespace std;

#define FOR(i,a,b)   for(int i=(a);i<(b);i++)
#define REP(i,a,b)   for(int i=(a);i<=(b);i++)

#define sz 1040

int N,M,cnt;
int cap[sz][sz],flow[sz][sz],parent[sz],s,t;
int vd[25][sz];
int top[25],pt[25];

void init_p()
{
int lim = N+M+5;
FOR(i,0,lim)parent[i]=-1;
}

//MAX-FLOW: FORD FULKERSON..RESIDUAL GRAPH
bool path()
{
int u;
queue<int> qu;
char color[sz];
init_p();
memset(color,0,sizeof(color));
color[s] = 1;
qu.push(s);
while(qu.empty()==false)
{
u = qu.front();
qu.pop();
REP(i,1,t)
{
if((cap[u][i]-flow[u][i])>0 && color[i]==0)
{
color[i] = 1;
parent[i] = u;
qu.push(i);
if(i==t)break;
}
}
if(color[t]==1)break;
}
if(color[t]==0)return false;
int now,previous;
now =t;
while(parent[now] != -1)
{
previous = parent[now];
if(previous>0 && previous<=N && now>N && now<t)
{
vd[previous][top[previous]++] = now;
}
flow[previous][now] += 1;
flow[now][previous] = -flow[previous][now];
now = previous;
}
return true;
}

void init()
{
int lim = N+M+5;
FOR(i,0,lim)
{
FOR(j,0,lim)
{
cap[i][j] = flow[i][j] = 0;
}
}
REP(i,0,N+2)
{
top[i] = 0;
}
}

int main()
{
//	  freopen("10092.in","r",stdin);
int capacity,l,val;
while(1)
{
scanf("%d %d",&N,&M);
if(N==0 && M==0)break;
s = capacity = 0;
init();
REP(i,1,N)
{
scanf("%d",&cap[s][i]);
pt[i] = cap[s][i];
capacity += cap[s][i];
}
t = N+M+1;
FOR(i,N+1,t)
{
scanf("%d",&l);
FOR(j,0,l)
{
scanf("%d",&val);
cap[val][i] = 1;
}
}
FOR(i,N+1,t)
{
cap[i][t] = 1;
}
cnt = 0;
while(path()==true)
{
cnt++;
}
if(cnt<capacity)
{
printf("0\n");
continue;
}
printf("1\n");
int li,prob;
REP(i,1,N)
{
li = top[i];
prob = pt[i];
FOR(j,0,prob)
{
if(j>0)printf(" %d",vd[i][li-pt[i]]-N);
else printf("%d",vd[i][li-pt[i]]-N);
pt[i]--;
}
printf("\n");
}
}
return 0;
}
``````