Submission #812516

#	Time	Username	Problem	Language	Result	Execution time	Memory
812516		andrei_boaca	Thousands Islands (IOI22_islands)	C++17	3.50 / 100	62 ms	37264 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
//#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
struct date
{
    int nod,a,b;
};
vector<date> muchii[100005];
vector<int> c[1005][1005];
bool useedge[300005],usenod[300005];
int n,m;
bool good=0;
void dfs(int nod)
{
    if(good)
        return;
    usenod[nod]=1;
    for(date i:muchii[nod])
    {
        if(good)
            return;
        if(!useedge[i.a]&&!useedge[i.b])
        {
            if(usenod[i.nod])
            {
                good=1;
                return;
            }
            else
            {
                useedge[i.a]=1;
                useedge[i.b]=1;
                dfs(i.nod);
                useedge[i.a]=0;
                useedge[i.b]=0;
            }
        }
    }
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V)
{

    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        int a=U[i];
        int b=V[i];
        c[a][b].push_back(i);
    }
    if(n==2)
    {
        if(c[0][1].size()>=2&&c[1][0].size()>=1)
            return true;
        return false;
    }
    for(int a=0;a<n;a++)
        for(int b=0;b<n;b++)
            if(a!=b)
            {
                for(int i=0;i<c[a][b].size()&&i<c[b][a].size();i++)
                {
                    int x=c[a][b][i];
                    int y=c[b][a][i];
                    muchii[a].push_back({b,x,y});
                }
            }
    dfs(0);
    return good||muchii[0].size()>=2;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:65:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for(int i=0;i<c[a][b].size()&&i<c[b][a].size();i++)
      |                             ~^~~~~~~~~~~~~~~
islands.cpp:65:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for(int i=0;i<c[a][b].size()&&i<c[b][a].size();i++)
      |                                               ~^~~~~~~~~~~~~~~

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45