10511 - Councilling

[brianfry713]

Impossible should have a period at the end.

[forthright48]

Haha. Sorry about that. Thanks for noticing the bug. I fixed it but still WA. Maybe I should solve more Bipartite Matching problems and then come back to this later.

[forthright48]

After 20 submission, I finally found out why I was getting WA. Guys, be careful. Each person will have unique name, BUT, a person name can be same as a party or club. A party name can also be same as club name. We have to count them as different.

1

a a a
b b b
c c c

Answer is
a a
b b
c c

[nbacool2]

Hi, fellas. I used Edmond-Karp's Max flow algorithm for solving the problem and hashing with open addressing for storing the strings of the clubs and parties. I solve the sample test caces correctly but I get WA on the judge. Any ideas what could be wrong?
GOT AC AND CODE REMOVED

[brianfry713]

If the last test case is Impossible, don't print a blank line after it.

[nbacool2]

If the last test case is Impossible, don't print a blank line after it.

OK, I edited my code and fixed that but I still get WA

[brianfry713]

Input:

Code: Select all

1

a d q d b h
b g e k h r m w t n p
c h m n x v d w r b s l g k h u f j c p a q e o
d c r s e u k g c w l b a n d p q
e b g a
f e j s f q c l w u n i b o d
g i g
h f w a n o e g x d m k r q h t l s u f
i j i d x b s w j q f e t
j i p f q a i g s e j r b w v t u o n l m d h x
k l u w h
l f f h l t k n a w
m i k o h e l g t v x f b m r u w i q d n c j p
n h k l g w e c j
o f o t g v c f r b l p e m i h q u d s w x n j a
p e u c t v
q d s d o x
r b b c f h r n d l v p w s a k t i
s h r k i q s o h v l m b d
t d u b w d s a n f v o t x p k q h e c l r i j g m
u d s c n g h b a q x j p u
v f x o g l m k t i n w j s u d p a r e h
w b f e j x n b a d g w o c v l r p h i k m
x g k g j w f x b t c u q m v a o d e
y a i

AC output:

Code: Select all

a d
b e
c k
d r
f b
g g
h m
i t
j p
k h
l n
m v
n w
o q
p u
q x
r s
s l
t f
u c
v j
w a
x o
y i

[nbacool2]

I made some changes to my code (I updated my previous post with the code) and my program produces a correct output for your test case but I still get WA. This starts getting so annoying

[brianfry713]

Input:

Code: Select all

1

a a a
b b a
c c a

Output should be Impossible.

[nbacool2]

brianfry713, you're awesome, dude. Thanks a lot . Got AC

[cshung_test]

Beware of input where a club is listed twice in the club list.

PersonA PartyA ClubA ClubA

After taking care of this I've got AC.

Original code and analysis deleted after AC

[BlackBeard]

I tried max flow algorithm, but got WA.
My algo:
source->every club(capacity=1);
clubs->their people(capacity=1);
people->their party(capacity=1);
party->sink(capacity=(Club numbers-1)/2);
if(flow!=club_number) print "Impossible" else, print solution.

I think the algorithm is correct and tried all the above inputs. Please help...

Code: Select all

#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define scs(x) scanf("%s",x)
#define pr(x) printf("%d",x)
#define prn(x) printf("%d\n",x)
#define memc(x,y) memcpy(&x,&y,sizeof(x))
#define mems(x,y) memset(x,y,sizeof(x))
#define fli() freopen("in.txt","r",stdin)
#define flo() freopen("out.txt","w",stdout)
#define rep(i,v) for(int i=0;i<v;i++)
#define Repe(i,x,v) for(int i=x;i<=v;i++)
#define repv(i,x) for(auto i=x.begin();i!=x.end();i++)
#define reprv(i,x) for(auto i=x.rbegin();i!=x.rend();i++)
#define what_is(x) cerr << #x << " is " << x << endl
#define pb push_back
#define bl putchar('\n')
#define gcc getchar()
#define pcc putchar
#define si size
#define fi first
#define se second
#define MAX 3050
#define source 3010
#define sink 3011
typedef long long ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef std::pair<int,int> ii;
using namespace std;

int graph[MAX][MAX],r_graph[MAX][MAX],parent[MAX],node_no,edge_no,ans;
bool visited[MAX],al[MAX][MAX];
char st[100],nm[100],pr[100],cl[100];
int nm_id,pr_id,cl_id  ,name,party,club;
map<string,int>pr_node,cl_node;
vector<ii>com;
vector<pair<string,string>>coms;

bool bfs(int s, int t){
    memset(visited, 0, sizeof(visited));
    queue <int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty()){
        int u = q.front();
        q.pop();

        for (int v=0; v<cl_id; v++){
            if (visited[v]==false && r_graph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
        for (int v=1000; v<nm_id; v++){
            if (visited[v]==false && r_graph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
        for (int v=2000; v<pr_id; v++){
            if (visited[v]==false && r_graph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
        if(visited[t]==0 and r_graph[u][t]>0){
            visited[t]=1;
            parent[t]=u;
            break;
        }
    }

    return (visited[t] == true);
}

int edmonds_karp(int s, int t){
    int u, v;

    memc(r_graph,graph);

    int max_flow = 0;

    while (bfs(s, t)){
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v]){
            u = parent[v];
            path_flow = min(path_flow, r_graph[u][v]);
        }

        for (v=t; v != s; v=parent[v]){
            u = parent[v];
            r_graph[u][v] -= path_flow;
            r_graph[v][u] += path_flow;
        }
        max_flow += path_flow;
    }

    return max_flow;
}

void reset(){
    com.clear();
    coms.clear();
    pr_node.clear();
    cl_node.clear();
    mems(graph,0);
    mems(r_graph,0);
    mems(parent,-1);
    mems(al,0);
}

int main(){
//    fli();
    int t,u,v,w;
    sc(t);
    gcc;
    gcc;
    while(t--){
        reset();
        nm_id=1000;
        pr_id=2000;
        cl_id=0;
        while(gets(st)){
            if(strlen(st)==0)break;
            stringstream ss(st);
            ss>>nm;
            name=nm_id++;
            ss>>pr;
            if(pr_node.find(pr)==pr_node.end()){
                party=pr_id;
                pr_node[pr]=pr_id++;
            }else{
                party=pr_node[pr];
            }
            graph[name][party]=1;
            graph[party][sink]=1;
            while(ss>>cl){
                if(cl_node.find(cl)==cl_node.end()){
                    club=cl_id;
                    cl_node[cl]=cl_id++;
                }else{
                    club=cl_node[cl];
                }
                graph[source][club]=1;
                graph[club][name]=1;
                al[club][name]=1;
                com.pb({club,name});
                coms.pb({cl,nm});
            }
        }
        w=(cl_node.si()-1)/2;
        repv(i,pr_node){
            graph[i->se][sink]=w;
        }
        ans=edmonds_karp(source,sink);
        if(ans!=cl_node.si()){
            puts("Impossible.");
        }else{
            rep(i,com.si()){
                if( r_graph[com[i].fi][com[i].se]==0 and al[com[i].fi][com[i].se] ){
                    printf("%s %s\n",coms[i].se.c_str(),coms[i].fi.c_str());
                }
            }
        }

        if(t) bl;
    }
    return 0;
}