Posted: Mon Jun 26, 2006 11:37 pm
I've re-rejudged every submission, so the submissions above 10 seconds will dissapear. Process will take 3-4 days, since I can't rejudge right now.
Welcome Carlos,
It should be.
Page 2 of 3
Posted: Tue Jun 27, 2006 11:08 am
563 - Runtime Error
Posted: Wed Oct 25, 2006 6:33 pm
Hi. I'm receiving Runtime Error (Inavlid Memory Reference) for about 2 days and can't find where this invalid memory reference can be happening.
Thanks for your help =)
Here's my code (I tried an algorithm that looks like max bipartite matching)
[/code]
Thanks for your help =)
Here's my code (I tried an algorithm that looks like max bipartite matching)
Code: Select all
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
int vis[55][55];
int antx[55][55];
int anty[55][55];
int bank[55][55];
int nvis;
int dirx[] = {1,0,-1,0};
int diry[] = {0,1,0,-1};
int nx, ny;
#define f(i,j,k) for(int i = j; i < k; i++)
#define sz size
#define pb push_back
int dfs(int x, int y){
vis[x][y] = nvis;
int xx, yy;
if(x == 0 || y == 0 || x > nx || y > ny) return 1;
f(i,0,4){
xx = x + dirx[i];
yy = y + diry[i];
if(bank[xx][yy]) continue;
if(vis[xx][yy] >= nvis) continue;
if(antx[xx][yy] == x && anty[xx][yy] == y) continue;
if(anty[xx][yy] == -1 && antx[xx][yy] == -1){
if(dfs(xx,yy)){
antx[xx][yy] = x;
anty[xx][yy] = y;
return 1;
}
else continue;
}
if(dfs(antx[xx][yy],anty[xx][yy])){
antx[xx][yy] = x;
anty[xx][yy] = y;
return 1;
}
}
return 0;
}
vector<int> bx, by;
int main(void){
int n;
scanf("%d",&n);
while(n--){
int b;
scanf("%d %d %d",&nx,&ny,&b);
f(i,0,55) f(j,0,55) bank[i][j]=0;
bx.clear(); by.clear();
int is = 1;
f(i,0,b){
int a,c;
scanf("%d %d",&a,&c);
bx.pb(a); by.pb(c);
if(bank[a][c]){
is = 0;
goto end;
}
bank[a][c]=1;
}
f(i,0,55) f(j,0,55) { vis[i][j] = 0; anty[i][j]=antx[i][j]=-1; }
nvis = 0;
f(i,0,b){
nvis++;
if(!dfs(bx[i],by[i])){
is=0;
break;
}
}
end:;
if(is) printf("possible\n");
else printf("not possible\n");
}
return 0;
}
MaxFlow Algorithm and Problem 563-CrimeWave
Posted: Tue Dec 12, 2006 4:37 pm
The problem 563-CrimeWave is a maximum
flow problem. The funny thing is i've AC
for this problem although i think my solution
is wrong in the way it implements ford-fulkerson
algorithm!!!
Since vertices also have capacities in this
problem, i had the usual idea of splitting
the vertices into two and have the newly
created edge the vertex capacity. But i just
couldn't find a way to split the vertices.
I know it sounds funny, but given the grid like
graph structure it seem very complicated to
split the vertices, and to add pain, this is
an undirected graph.
Finding no other way and since the capacity of
all the vertices is exactly 1, i thought of
using a 'visited' array just to mark an already
visited vertex and never to use it while finding
a new augmenting path. However the way ford-fulkerson
algorithm works i thougth it was incorrect to
do this. BUT it was AC!!
now i've two questions.
(1) is my approach correct or incorrect? why?
(2) how can i split the vertices of an undirected
graph like the one below to accomodate vertex capacities?
Thanks.
flow problem. The funny thing is i've AC
for this problem although i think my solution
is wrong in the way it implements ford-fulkerson
algorithm!!!
Since vertices also have capacities in this
problem, i had the usual idea of splitting
the vertices into two and have the newly
created edge the vertex capacity. But i just
couldn't find a way to split the vertices.
I know it sounds funny, but given the grid like
graph structure it seem very complicated to
split the vertices, and to add pain, this is
an undirected graph.
Finding no other way and since the capacity of
all the vertices is exactly 1, i thought of
using a 'visited' array just to mark an already
visited vertex and never to use it while finding
a new augmenting path. However the way ford-fulkerson
algorithm works i thougth it was incorrect to
do this. BUT it was AC!!
now i've two questions.
(1) is my approach correct or incorrect? why?
(2) how can i split the vertices of an undirected
graph like the one below to accomodate vertex capacities?
Code: Select all
0---0---0
| | |
0---0---0
| | |
0---0---0Posted: Sat Dec 30, 2006 8:01 pm
Hi,
I don't understand the fact that a bank can be robbed more than once ... I did exactly same as ImLazy has written above but I always get WA
. My programs output matches with the above output on all the 50 cases [ I suppose the output shown above is correct ]. Can somebody help me out about it. Here is the code for you to have a look =>
Thanks a lot in advance.
I don't understand the fact that a bank can be robbed more than once ... I did exactly same as ImLazy has written above but I always get WA
. My programs output matches with the above output on all the 50 cases [ I suppose the output shown above is correct ]. Can somebody help me out about it. Here is the code for you to have a look =>
Code: Select all
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<stack>
#include<algorithm>
#include<queue>
#include<list>
#include<map>
#include<cassert>
using namespace std;
/* maximum Flow using Ford Fulkerson method */
#define INF 10000000
int n,source,destination;
list<pair<int,int> > graph[5002];
int calCapacity(int a,int b){
for(list<pair<int,int> >::iterator i=graph[a].begin();i!=graph[a].end();i++){
if((*i).first == b){
return (*i).second;
}
}
return 0;
}
void updateCapacity(int a,int b,int c){
bool state = false;
for(list<pair<int,int> >::iterator i=graph[a].begin();i!=graph[a].end();i++){
if((*i).first == b){
(*i).second += c;
if((*i).second == 0){
graph[a].erase(i);
return;
}
state = true;
break;
}
}
if(!state){
graph[a].push_front(pair<int,int> (b,c));
}
return;
}
int bfsCapacity(){
queue<int> q;
bool visited[n],done=false;
int from[n],cur,where,pathCapacity,prev;
memset(visited,false,sizeof(visited));
from[destination] = from[source] = -1;
q.push(source);
visited[source] = true;
while(!q.empty() && !done){
cur = q.front();q.pop();
for(list<pair<int,int> >::iterator i=graph[cur].begin();i!=graph[cur].end();i++){
if(!visited[(*i).first] && (*i).second > 0){
visited[(*i).first] = true;
q.push((*i).first);
from[(*i).first] = cur;
if((*i).first == destination){
done = true;
}
}
}
}
if(!visited[destination]){
return 0;
}
where = destination;
pathCapacity = INF;
while(from[where] > -1){
pathCapacity = min(pathCapacity,calCapacity(from[where],where));
where = from[where];
}
where = destination;
while(from[where] > -1){
prev = from[where];
updateCapacity(from[where],where,-pathCapacity);
updateCapacity(where,from[where],pathCapacity);
where = from[where];
}
assert(pathCapacity == 1);
return pathCapacity;
}
int maxFlow(){
int answer = 0,p;
while(1){
p = bfsCapacity();
if(!p){
break;
}
answer += p;
}
return answer;
}
int main(){
int N,row,column,c,x,y;
scanf("%d",&N);
while(N--){
scanf("%d%d%d",&column,&row,&c);
source = 0;
destination = 2 * row * column + 1;
n = 2 * row * column + 2;
for(int i=0;i<n;i++){
graph[i].clear();
}
for(int i=0;i<c;i++){
scanf("%d%d",&y,&x);
x = row - x;
graph[source].push_front(pair<int,int> ((x*column + y)*2-1,1));
}
for(int i=0;i<row;i++){
for(int j=1;j<=column;j++){
graph[(i*row+j)*2-1].push_front(pair<int,int> ((i*column+j)*2,1));
if ( i > 0){
graph[(i*column+j)*2].push_front(pair<int,int> (((i-1)*column+(j))*2-1,1));
}
if ( i < row-1 ){
graph[(i*column+j)*2].push_front(pair<int,int> (((i+1)*column+(j))*2-1,1));
}
if ( j > 1){
graph[(i*column+j)*2].push_front(pair<int,int> (((i)*column+(j-1))*2-1,1));
}
if ( j < column ){
graph[(i*column+j)*2].push_front(pair<int,int> (((i)*column+(j+1))*2-1,1));
}
if(i == 0 || i == row - 1 || j == 1 || j == column){
graph[(i*column+j)*2].push_front(pair<int,int> (destination,1));
}
}
}
if(maxFlow() == c){
puts("possible");
}
else {
puts("not possible");
}
}
return 0;
}Posted: Thu Aug 23, 2007 12:20 pm
I am a bit confused with the problem statement . Can a bank be robbed more than once ?? If a bank is being robbed for the second time , doest it men that the second robbers are crossing the first robbers' path ??
I am getting WA . I used backtracking to match the paths . I got correct answer for the 50 inputs given in this thread. Can anyone hep me with some more tricky input ??
I am getting WA . I used backtracking to match the paths . I got correct answer for the 50 inputs given in this thread. Can anyone hep me with some more tricky input ??
Posted: Fri Aug 24, 2007 5:21 am
What they meant was that in the judge input, there may be cases where the same bank is listed twice. In those cases, always output not possible.
I've verified it using assert().
I've verified it using assert().
Posted: Fri Aug 24, 2007 7:00 pm
Is there anyone who can explain the algorithm for this problem ?? I think , I have to calculate repeatedly changing source and sink and then pick the smallest flow. but I am a bit confused how to construct the graph and how to select the source and the sink . Can anyone help me ??
Posted: Fri Aug 24, 2007 8:04 pm
Use two artificial nodes, source and sink. capacity of source to banks are all 1, and capacity of the corner points to sink are 1. Then run flow from source to sink. Hope it helps.
Posted: Mon Sep 03, 2007 5:48 am
should I split every node into two nodes with capacity 1 between them to avoid the collision ???
if YES , then the number of nodex get doubled and I am afraid , I will face a TLE .
if YES , then the number of nodex get doubled and I am afraid , I will face a TLE .
Posted: Tue Feb 19, 2008 9:09 am
for ImLazy's input my solution gives exactly same output as mf's output. But I am getting Wrong Answer. Can anyone give some more tricky inputs.
Posted: Tue Feb 19, 2008 3:18 pm
I don't have any input cases. But if you make and post some inputs, I'll be happy to give you output of my accepted program.
If your algorithm is like the one described by ImLazy, then it basically should be correct, look for minor bugs in your code.
If your algorithm is like the one described by ImLazy, then it basically should be correct, look for minor bugs in your code.
Posted: Wed Feb 20, 2008 8:38 am
Thanks mf.
Now I am providing my max-flow values of ImLazy's inputs, Please verify these.
(I am not very good at maximum flow, If you want i can paste my code here)
Now I am providing my max-flow values of ImLazy's inputs, Please verify these.
Code: Select all
(flow: 12) not possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 12) not possible
(flow: 4) not possible
(flow: 11) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 9) not possible
(flow: 11) not possible
(flow: 15) not possible
(flow: 9) not possible
(flow: 13) not possible
(flow: 8) not possible
(flow: 6) possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 7) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 14) not possible
(flow: 11) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 9) not possible
(flow: 6) possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 14) not possible
(flow: 15) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 9) not possible
(flow: 3) not possible
(flow: 7) not possible
(flow: 13) not possible
(flow: 12) not possible
(flow: 3) possible
Posted: Thu Feb 21, 2008 5:44 am
For this case my program found a flow of value 10, while your program says 9.
Code: Select all
1
5 5 13
4 5
1 5
3 3
1 3
4 2
3 1
4 2
4 4
1 4
2 3
1 3
4 5
2 4
Posted: Fri Feb 22, 2008 11:41 am
Thanks again mf,
After fixing some bug, i got these output for same input.
But I am still getting Wrong Answer. Are above outputs are correct?
After fixing some bug, i got these output for same input.
Code: Select all
(flow: 12) not possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 12) not possible
(flow: 4) not possible
(flow: 11) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 9) not possible
(flow: 11) not possible
(flow: 15) not possible
(flow: 9) not possible
(flow: 13) not possible
(flow: 8) not possible
(flow: 6) possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 7) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 14) not possible
(flow: 11) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 9) not possible
(flow: 6) possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 14) not possible
(flow: 15) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 10) not possible
(flow: 3) not possible
(flow: 7) not possible
(flow: 13) not possible
(flow: 12) not possible
(flow: 3) possible