Submission #845827

#	Time	Username	Problem	Language	Result	Execution time	Memory
845827		Marco_Escandon	Thousands Islands (IOI22_islands)	C++17	24 / 100	61 ms	14264 KiB

islands

#include<bits/stdc++.h>
using namespace std;
#include <vector>
typedef int ll;

#include <variant>
#include <vector>
vector<ll> cad[100001];
ll v[100001]={ };
ll v2[100001]={};
ll pi=0;
ll pl=0;
ll ap=0;
void sol(ll node, ll p)
{
    if(pl==1)
        return ;
    if(v[node]!=0)
    {
        ap=v[node];
        pi=node;
        v[node]=p;
        pl=1;
        return ;
    }
    if(v2[node]!=0)
        return;
    v2[node]=1;
    v[node]=p;
    for(auto i:cad[node])
    {
        sol(i,node);
    }
    if(pi==0)
    {
        v[node]=0;
    }
}
std::variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U, std::vector<int> V)
{
    map<pair<ll,ll>,ll> mapa;
    for(int i=0; i<m; i++)
        if(i%2==0)
        {
            cad[U[i]+1].push_back(V[i]+1);
            mapa[{U[i]+1,V[i]+1}]=i;
        }
    sol(1,-1);
    if(pi==0)
    {
        return false;
    }
    vector<ll>asdf;
    asdf.push_back(pi);
    while(ap!=1&&ap!=0)
    {
        asdf.push_back(ap);
        ap=v[ap];
    }
    asdf.push_back(ap);
    reverse(asdf.begin(),asdf.end());
    vector<ll> sol,s2,sol2,sade;
    if(ap!=0)
    for(int i=0; i<asdf.size()-1; i++)
    {
        s2.push_back(mapa[{asdf[i],asdf[i+1]}]);
        sade.push_back(mapa[{asdf[i],asdf[i+1]}]);
    }
    ll p=pi;
    vector<ll> st;
    st.push_back(p);
    p=v[p];
    while(p!=pi)
    {
        st.push_back(p);
        p=v[p];
    }
    st.push_back(p);
    //cout<<st.size()<<"\n";
    reverse(st.begin(),st.end());
    for(int i=0; i<st.size()-1; i++)
    {
        sol.push_back(mapa[{st[i],st[i+1]}]);
        s2.push_back(mapa[{st[i],st[i+1]}]);
    }
    reverse(sol.begin(),sol.end());
    for(int i=0; i<st.size()-1; i++)
    {
        sol2.push_back(mapa[{st[i],st[i+1]}]+1);
        s2.push_back(mapa[{st[i],st[i+1]}]+1);
    }
    reverse(sol2.begin(),sol2.end());
    reverse(sade.begin(),sade.end());
    for(auto i:sol)
        s2.push_back(i);
    for(auto i:sol2)
        s2.push_back(i);
    for(auto i:sade)
        s2.push_back(i);
    return s2;
}

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:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0; i<asdf.size()-1; i++)
      |                  ~^~~~~~~~~~~~~~
islands.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0; i<st.size()-1; i++)
      |                  ~^~~~~~~~~~~~
islands.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0; i<st.size()-1; i++)
      |                  ~^~~~~~~~~~~~

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