oj.uz

Submission #581341

# Submission time Handle Problem Language Result Execution time Memory
581341 2022-06-22T13:46:12 Z yutabi Marriage questions (IZhO14_marriage) C++14
40 / 100
 300 ms 6452 KB 
#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=0;j<path.size()-1;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]);

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

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

    printf("%d",ans);
}

Compilation message

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:155:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |                     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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 0 ms 212 KB Output isn't correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 1 ms 212 KB Output isn't correct
24 Incorrect 1 ms 212 KB Output isn't correct
25 Incorrect 6 ms 732 KB Output isn't correct
26 Incorrect 2 ms 340 KB Output isn't correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Incorrect 4 ms 724 KB Output isn't correct
30 Incorrect 3 ms 596 KB Output isn't correct
31 Incorrect 16 ms 1760 KB Output isn't correct
32 Incorrect 5 ms 468 KB Output isn't correct
33 Correct 3 ms 356 KB Output is correct
34 Correct 5 ms 340 KB Output is correct
35 Incorrect 23 ms 1768 KB Output isn't correct
36 Incorrect 21 ms 1512 KB Output isn't correct
37 Incorrect 26 ms 2184 KB Output isn't correct
38 Incorrect 35 ms 2784 KB Output isn't correct
39 Correct 147 ms 716 KB Output is correct
40 Correct 103 ms 1044 KB Output is correct
41 Incorrect 87 ms 1556 KB Output isn't correct
42 Incorrect 55 ms 2380 KB Output isn't correct
43 Incorrect 66 ms 3220 KB Output isn't correct
44 Incorrect 135 ms 4812 KB Output isn't correct
45 Incorrect 235 ms 2904 KB Output isn't correct
46 Incorrect 231 ms 6052 KB Output isn't correct
47 Incorrect 226 ms 6392 KB Output isn't correct
48 Incorrect 225 ms 5736 KB Output isn't correct
49 Incorrect 243 ms 6452 KB Output isn't correct
50 Correct 300 ms 1416 KB Output is correct