oj.uz

Submission #581346

# Submission time Handle Problem Language Result Execution time Memory
581346 2022-06-22T13:52:21 Z yutabi Marriage questions (IZhO14_marriage) C++14
66 / 100
 180 ms 6548 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++)
        {
            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

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.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 1 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 Correct 0 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 5 ms 416 KB Output is correct
26 Incorrect 1 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 Correct 19 ms 596 KB Output is correct
32 Incorrect 4 ms 468 KB Output isn't correct
33 Correct 2 ms 340 KB Output is correct
34 Correct 4 ms 384 KB Output is correct
35 Correct 62 ms 888 KB Output is correct
36 Correct 68 ms 872 KB Output is correct
37 Correct 60 ms 724 KB Output is correct
38 Incorrect 112 ms 2696 KB Output isn't correct
39 Correct 86 ms 724 KB Output is correct
40 Correct 77 ms 1084 KB Output is correct
41 Incorrect 69 ms 1580 KB Output isn't correct
42 Incorrect 38 ms 2380 KB Output isn't correct
43 Incorrect 44 ms 3272 KB Output isn't correct
44 Incorrect 139 ms 4812 KB Output isn't correct
45 Incorrect 152 ms 2888 KB Output isn't correct
46 Incorrect 131 ms 6040 KB Output isn't correct
47 Incorrect 160 ms 6196 KB Output isn't correct
48 Incorrect 165 ms 5752 KB Output isn't correct
49 Incorrect 163 ms 6548 KB Output isn't correct
50 Correct 180 ms 1152 KB Output is correct