Submission #832570

#	Time	Username	Problem	Language	Result	Execution time	Memory
832570		Kaitokid	Thousands Islands (IOI22_islands)	C++17	100 / 100	115 ms	25724 KiB

islands

#include <bits/stdc++.h>
using namespace std;
int dg[100009];
vector<int>to[100009],frm[100009];
int ed[200009][2];
bool incy[200009],vsnd[200009],dl[200009];
vector<int>tocy[2],cy[2];
bool fnd;
void dfs(int x,int u)
{
    //cout<<x<<" "<<tocy[u].back()<<" "<<u<<endl;
    if(fnd||(vsnd[x]==2))return;
    if(vsnd[x]==1)
    {
        fnd=true;
        while(ed[tocy[u].back()][0]!=x){cy[u].push_back(tocy[u].back());tocy[u].pop_back();}

        cy[u].push_back(tocy[u].back());tocy[u].pop_back();
        reverse(cy[u].begin(),cy[u].end());
        return;
    }
 vsnd[x]=1;
 for(auto v:frm[x])
        {if(!dl[ed[v][1]]){tocy[u].push_back(v);dfs(ed[v][1],u);if(fnd)return ;tocy[u].pop_back();}}
 vsnd[x]=2;
}
variant<bool,vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V)
{
    for(int i=0;i<M;i++)
    {
        ed[i][0]=U[i];
        ed[i][1]=V[i];
        frm[U[i]].push_back(i);
        to[V[i]].push_back(i);
        dg[U[i]]++;
    }
    queue<int>qq;
    for(int i=0;i<N;i++)
        if(dg[i]==0)qq.push(i);
    while(!qq.empty())
    {
        int u=qq.front();
        qq.pop();
        dl[u]=1;
        for(auto v:to[u])
        {
            dg[ed[v][0]]--;
            if(dg[ed[v][0]]==0)qq.push(ed[v][0]);
        }
    }
    if(dl[0])return false;
    int h=0,u=-1,v=-1;
    vector<int>gg;
    while(true)
    {

        vector<int>bb;
        for(auto w:frm[h])
            if((!dl[ed[w][1]]))bb.push_back(w);
        if(bb.empty())return false;
        if(bb.size()==1)
        { qq.push(h);
        while(!qq.empty())
    {
        int uu=qq.front();
        qq.pop();
        dl[uu]=1;
        for(auto vv:to[uu])
        {
            dg[ed[vv][0]]--;
            if((!dl[ed[vv][0]])&&dg[ed[vv][0]]==0)qq.push(ed[vv][0]);
        }

    }
            gg.push_back(bb[0]);
            h=ed[bb[0]][1];
            if(dl[h])return false;
            continue;
        }
        u=bb[0],v=bb[1];
        break;
    }
    dl[h]=0;
    vsnd[h]=1;
    tocy[0].push_back(u);
    fnd=false;
    dfs(ed[u][1],0);
    memset(vsnd,0,sizeof vsnd);
    fnd=false;
    vsnd[h]=1;
    tocy[1].push_back(v);
    dfs(ed[v][1],1);
/*cout<<h<<' '<<u<<" "<<v<<" "<<ed[u][1]<<" "<<ed[v][1]<<endl;
      cout<<"to ";
        for(auto w:gg)cout<<w<<" ";
        cout<<endl;
        cout<<"tocy0 ";
        for(auto w:tocy[0])cout<<w<<" ";
        cout<<endl;
        cout<<"cy0 ";
        for(auto w:cy[0])cout<<w<<" ";
        cout<<endl;

        cout<<"tocy1 ";
        for(auto w:tocy[1])cout<<w<<" ";
        cout<<endl;
        cout<<"cy1 ";
        for(auto w:cy[1])cout<<w<<" ";
        cout<<endl;

      //  return {-1};*/
     // if((cy[0].empty())||(cy[1].empty()))return false;
    vector<int>ans=gg;
    for(auto w:tocy[0])ans.push_back(w);
    for(auto w:cy[0]){ans.push_back(w);incy[w]=1;}
    reverse(tocy[0].begin(),tocy[0].end());
    for(auto w:tocy[0])ans.push_back(w);
    reverse(tocy[0].begin(),tocy[0].end());
    int rr=-1;
    vector<int>f;
    for(auto w:tocy[1])
    {
        if(incy[w]){rr=w;break;}
        f.push_back(w);
    }
    if(rr==-1)
    {
     for(auto w:cy[1])
    {
        if(incy[w]){rr=w;break;}
        f.push_back(w);
    }
    }
    if(rr==-1)
    {
      for(auto w:tocy[1]) ans.push_back(w);
       for(auto w:cy[1])ans.push_back(w);
       reverse(tocy[1].begin(),tocy[1].end());
       for(auto w:tocy[1])ans.push_back(w);
       reverse(tocy[1].begin(),tocy[1].end());
        for(auto w:tocy[0])ans.push_back(w);
        reverse(cy[0].begin(),cy[0].end());
        for(auto w:cy[0])ans.push_back(w);
        reverse(tocy[0].begin(),tocy[0].end());
        for(auto w:tocy[0])ans.push_back(w);
       for(auto w:tocy[1])ans.push_back(w);
       reverse(cy[1].begin(),cy[1].end());
       for(auto w:cy[1])ans.push_back(w);
       reverse(tocy[1].begin(),tocy[1].end());
       for(auto w:tocy[1])ans.push_back(w);
       reverse(tocy[1].begin(),tocy[1].end());
       reverse(gg.begin(),gg.end());
        for(auto w:gg)ans.push_back(w);
        return ans;


    }
    for(auto w:f)ans.push_back(w);
    for(int i=0;i<cy[0].size();i++)
    {
        if(cy[0][i]!=rr)continue;
        for(int j=i-1;j>=0;j--)ans.push_back(cy[0][j]);
        for(int j=cy[0].size()-1;j>=i;j--)ans.push_back(cy[0][j]);
         reverse(f.begin(),f.end());
        for(auto w:f)ans.push_back(w);
        reverse(gg.begin(),gg.end());
        for(auto w:gg)ans.push_back(w);
        return ans;
    }
}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int, int)':
islands.cpp:12:21: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
   12 |     if(fnd||(vsnd[x]==2))return;
      |              ~~~~~~~^~~
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:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i=0;i<cy[0].size();i++)
      |                 ~^~~~~~~~~~~~~
islands.cpp:37:15: warning: control reaches end of non-void function [-Wreturn-type]
   37 |     queue<int>qq;
      |               ^~

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