Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

why wrong on 23
Author: ata
ID: 059912
Problem: 190
Contest: 0
Date: 2014-09-17 16:21:01

#include<bits/stdc++.h>

using namespace std;

const int Maxn=40*40+10;

int n,p,c,matchl[Maxn],matchr[Maxn],cv,ch;
vector<int> com[2];
vector<pair<int,int> >ans[2];
bool mark[Maxn],adj[Maxn][Maxn];

inline void init()
{
for(int i=0;i<n*n;i++)
{
if(i>n-1)
adj[i][i-n]=1;
if(i<n*(n-1))
adj[i][i+n]=1;
if(i%n!=n-1)
adj[i][i+1]=1;
if(i%n!=0)
adj[i][i-1]=1;
}
}

void ca(int t1)
{
if(t1>n-1)
adj[t1-n][t1]=0;
if(t1<n*(n-1))
adj[t1+n][t1]=0;
if(t1%n!=0)
adj[t1-1][t1]=0;
if(t1%n!=n-1)
adj[t1+1][t1]=0;
}

inline void input()
{
cin>>n>>p;
init();
for(int i=0;i<p;i++)
{
int t1,t2;
cin>>t1>>t2;
t1=t1-1+(t2-1)*n;
//cerr<<t1<<endl;
mark[t1]=true;
ca(t1);
}
}

void DFS(int v,bool w)
{
mark[v]=true;
com[w].push_back(v);
for(int i=0;i<n*n;i++)
if(!mark[i]&&adj[v][i])
DFS(i,!w);
}

bool check()
{
for(int i=0;i<n*n;i++)
if(!mark[i])
{
//cerr<<i<<endl;
DFS(i,0);
if(com[0].size()!=com[1].size())
return false;
}
return true;
}

bool match(int v)
{
for(int i=0;i<n*n;i++)
if(adj[v][i])
{
if(mark[i])
continue;
mark[i]=true;
if(matchr[i]==-1||match(matchr[i]))
{
matchl[v]=i;
matchr[i]=v;
return true;
}
}
return false;
}

inline void make_match()
{
for(int i=0;i<com[0].size();i++)
if(matchl[com[0][i]]==-1)
{
memset(mark,0,sizeof mark);
match(com[0][i]);
}
}

inline void count()
{
for(int i=0;i<com[0].size();i++)
if(com[0][i]%n==matchl[com[0][i]]%n)
{
cv++;
int t1=min(com[0][i],matchl[com[0][i]]);
ans[1].push_back(make_pair(t1%n+1,t1/n+1));
}
else
{
ch++;
int t1=min(com[0][i],matchl[com[0][i]]);
ans[0].push_back(make_pair(t1%n+1,t1/n+1));
}
}

inline void solve()
{
if(!check())
return ;
memset(mark,0,sizeof mark);
for(int i=0;i<n*n;i++)
matchl[i]=matchr[i]=-1;
make_match();
count();

}

inline void output()
{
if(com[0].size()!=com[1].size())
{
cout<<"Non";
return;
}

cout<<"Yesn"<<ch<<endl;
for(int i=0;i<ch;i++)
cout<<ans[0][i].first<<" "<<ans[0][i].second<<endl;
cout<<cv<<endl;
for(int i=0;i<cv;i++)
cout<<ans[1][i].first<<" "<<ans[1][i].second<<endl;
}


/*inline void output()
{
for(int i=0;i<com[0].size();i++)
cerr<<com[0][i]<<" "<<matchl[com[0][i]]<<endl;
}*/

int main()
{
input();
solve();
output();
return 0;
}


see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-11-23 06:18:35Online Contester Team © 2002 - 2016. All rights reserved.