Submission #581346

#	Time	Username	Problem	Language	Result	Execution time	Memory
581346		yutabi	Marriage questions (IZhO14_marriage)	C++14	66 / 100	180 ms	6548 KiB

marriage

#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++)
        {
            if(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=0;j<path.size()-1;j++)
                    {
                        s[path[j]]=s[path[j+1]];
                    }

                    int nw=*(fr[i].begin());

                    for(int j=0;j<l[nw].size();j++)
                    {
                        fr[l[nw][j]].erase(nw);
                    }

                    s[i]=nw;

                    i=-1;

                    for(int j=0;j<m;j++)
                    {
                        flag[j]=0;
                    }
                }
            }
        }

        /*printf("\n%d %d %d\n",ptr1,ptr2,u);

        for(int i=0;i<m;i++)
        {
            printf("%d - ",s[i]);

            for(set<int>::iterator it=fr[i].begin();it!=fr[i].end();it++)
            {
                printf("%d ",*it);
            }

            printf("\n");
        }*/
    }

    printf("%d",ans);
}

Compilation message (stderr)

marriage.cpp: In function 'bool DFS(int)':
marriage.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<l[s[node]].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0;i<l[ptr2].size();i++)
      |                         ~^~~~~~~~~~~~~~~
marriage.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for(int i=0;i<l[ptr1].size();i++)
      |                         ~^~~~~~~~~~~~~~~
marriage.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 for(int i=0;i<l[ptr1].size();i++)
      |                             ~^~~~~~~~~~~~~~~
marriage.cpp:144:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |                     for(int j=0;j<path.size()-1;j++)
      |                                 ~^~~~~~~~~~~~~~
marriage.cpp:151:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |                     for(int j=0;j<l[nw].size();j++)
      |                                 ~^~~~~~~~~~~~~
marriage.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d %d %d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
marriage.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf(" %d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 66 / 100