# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
581334 | yutabi | Marriage questions (IZhO14_marriage) | C++14 | 280 ms | 7484 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
int m;
int k;
vector <vector <int> > l;
int ans;
vector <int> s;
vector <set <int> > fr;
vector <bool> flag;
int u;
vector <int> path;
bool DFS(int node)
{
flag[node]=1;
if(s[node]==-1)
{
path.pb(node);
return 1;
}
for(int i=0;i<l[s[node]].size();i++)
{
if(flag[l[s[node]][i]]==0)
{
bool res=DFS(l[s[node]][i]);
if(res==1)
{
path.pb(node);
return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
s=vector <int> (m,-1);
fr=vector <set <int> > (m);
flag=vector <bool> (m);
l=vector <vector <int> > (n);
for(int i=0;i<k;i++)
{
int a,b;
scanf(" %d %d",&a,&b);
a--,b--;
l[a].pb(b);
}
int ptr1=0;
int ptr2=0;
while(1)
{
if(u<m)
{
if(ptr2>=n)
{
break;
}
for(int i=0;i<l[ptr2].size();i++)
{
fr[l[ptr2][i]].insert(ptr2);
}
ptr2++;
}
else
{
ans+=n-ptr2+1;
int y=-1;
for(int i=0;i<l[ptr1].size();i++)
{
if(s[l[ptr1][i]]==ptr1)
{
u--;
s[l[ptr1][i]]=-1;
}
}
if(y==-1)
{
for(int i=0;i<l[ptr1].size();i++)
{
fr[l[ptr1][i]].erase(ptr1);
}
}
ptr1++;
}
for(int i=0;i<m;i++)
{
while(flag[i]==0 && fr[i].size()>0)
{
path.clear();
if(DFS(i))
{
u++;
/*if(ptr2==2)
{
printf("\n\n");
for(int j=0;j<path.size();j++)
{
printf("%d ",path[j]);
}
printf("\n\n%d\n",s[0]);
}*/
for(int j=path.size()-1;j>0;j--)
{
flag[path[j]]=0;
s[path[j]]=s[path[j-1]];
}
flag[i]=0;
int nw=*(fr[i].begin());
for(int j=0;j<l[nw].size();j++)
{
fr[l[nw][j]].erase(nw);
}
s[i]=nw;
}
}
}
/*printf("\n%d %d %d\n",ptr1,ptr2,u);
for(int i=0;i<m;i++)
{
printf("%d ",s[i]);
}
printf("\n");*/
}
printf("%d",ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |