Submission #812904

#	Time	Username	Problem	Language	Result	Execution time	Memory
812904		andrei_boaca	Thousands Islands (IOI22_islands)	C++17	55 / 100	68 ms	38584 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <algorithm>
#include <assert.h>
//#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef pair<int,int> pii;
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;
int who;
vector<int> edges,v;
vector<int> nodes,w;
vector<date> ee[100005];
void dfs(int nod)
{
    if(good)
        return;
    if(muchii[nod].size()>=3)
    {
        who=nod;
        good=1;
        return;
    }
    usenod[nod]=1;
    for(date i:muchii[nod])
    {
        if(good)
            return;
        if(!usenod[i.nod])
        {
            edges.push_back(i.a);
            dfs(i.nod);
            if(good)
                return;
        }
    }
}
vector<int> sol;
void build(int x,int y,int z)
{
    assert(x>=0&&y>=0&&z>=0);
    int A=c[x][y][0];
    int B=c[y][x][0];
    int C=c[x][z][0];
    int D=c[z][x][0];
    if(y==z)
    {
        C=c[x][z][1];
        D=c[z][x][1];
    }
    vector<int> aux={A,B,C,D,B,A,D,C};
    for(int i:aux)
        sol.push_back(i);
}
bool use[200005];
bool inst[200005];
vector<int> ciclu;
vector<int> lant;
int from[200005];
void calc(int nod)
{
    if(good)
        return;
    use[nod]=1;
    inst[nod]=1;
    for(date i:ee[nod])
    {
        if(good)
            return;
        if(use[i.nod])
        {
            if(inst[i.nod])
            {
                if(good==0)
                {
                    good=1;
                    int x=nod;
                    while(true)
                    {
                        ciclu.push_back(x);
                        if(x==i.nod)
                            break;
                        else
                            x=from[x];
                    }
                    while(true)
                    {
                        lant.push_back(x);
                        if(x==0)
                            break;
                        else
                            x=from[x];
                    }
                }
                return;
            }
        }
        else
        {
            from[i.nod]=nod;
            calc(i.nod);
        }
    }
    inst[nod]=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)
        {
            int A=c[1][0][0];
            int B=c[0][1][0];
            int C=c[0][1][1];
            sol={B,A,C,B,A,C};
            return sol;
        }
        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});
                }
            }
    if(muchii[0].size()>=2)
    {
        int x=0;
        int y=muchii[0][0].nod;
        int z=muchii[0][1].nod;
        build(x,y,z);
        return sol;
    }
    dfs(0);
    if(good)
    {
        for(int i:edges)
            sol.push_back(i);
        int x=who;
        int y=-1;
        int z=-1;
        for(date i:muchii[who])
            if(!usenod[i.nod])
            {
                if(y==-1)
                    y=i.nod;
                else
                    z=i.nod;
            }
        build(x,y,z);
        reverse(edges.begin(),edges.end());
        for(int i:edges)
            sol.push_back(i);
        return sol;
    }
    for(int a=0;a<n;a++)
        for(int b=0;b<n;b++)
        {
            if(c[a][b].size()>=2)
            {
                int x=c[a][b][0];
                int y=c[a][b][1];
                ee[a].push_back({b,x,y});
            }
        }
    good=0;
    calc(0);
    if(good)
    {
        sol.clear();
        reverse(ciclu.begin(),ciclu.end());
        reverse(lant.begin(),lant.end());
        assert(ciclu.size()>=2);
        for(int i=1;i<lant.size();i++)
            sol.push_back(c[lant[i-1]][lant[i]][0]);
        int lg=ciclu.size();
        for(int i=0;i<ciclu.size();i++)
        {
            int x=ciclu[i];
            int y=ciclu[(i+1)%lg];
            sol.push_back(c[x][y][0]);
        }
        for(int i=0;i<ciclu.size();i++)
        {
            int x=ciclu[i];
            int y=ciclu[(i+1)%lg];
            sol.push_back(c[x][y][1]);
        }
        for(int i=0;;i=(i-1+lg)%lg)
        {
            int x=ciclu[i];
            int y=ciclu[(i-1+lg)%lg];
            sol.push_back(c[y][x][0]);
            if(i==1)
                break;
        }
        for(int i=0;;i=(i-1+lg)%lg)
        {
            int x=ciclu[i];
            int y=ciclu[(i-1+lg)%lg];
            sol.push_back(c[y][x][1]);
            if(i==1)
                break;
        }
        reverse(lant.begin(),lant.end());
        for(int i=1;i<lant.size();i++)
            sol.push_back(c[lant[i]][lant[i-1]][0]);
        return sol;
    }
    return false;
}

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:143:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 for(int i=0;i<c[a][b].size()&&i<c[b][a].size();i++)
      |                             ~^~~~~~~~~~~~~~~
islands.cpp:143:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 for(int i=0;i<c[a][b].size()&&i<c[b][a].size();i++)
      |                                               ~^~~~~~~~~~~~~~~
islands.cpp:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         for(int i=1;i<lant.size();i++)
      |                     ~^~~~~~~~~~~~
islands.cpp:201:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         for(int i=0;i<ciclu.size();i++)
      |                     ~^~~~~~~~~~~~~
islands.cpp:207:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for(int i=0;i<ciclu.size();i++)
      |                     ~^~~~~~~~~~~~~
islands.cpp:230:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |         for(int i=1;i<lant.size();i++)
      |                     ~^~~~~~~~~~~~

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