Submission #1077963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077963		Hanksburger	Thousands Islands (IOI22_islands)	C++17	0 / 100	2 ms	4956 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int tin[100005], pre[100005], final[100005], scc[100005], sz[100005], flag[100005], visited[100005], t, cnt, ok, target, firsttime;
vector<int> ss, ans1, ans2, ans3, ans4, ans5, ans11, ans12, ans21, ans22;
vector<int> adj[100005], s, ans, ans3copy;
map<pair<int, int>, int> mp;
void dfs(int u)
{
    tin[u]=pre[u]=(++t);
    s.push_back(u);
    for (int v:adj[u])
    {
        if (!tin[v])
        {
            ss.push_back(mp[{u, v}]);
            dfs(v);
            ss.pop_back();
            if (ok)
                break;
            if (flag[v])
                flag[u]=flag[v];
            pre[u]=min(pre[u], pre[v]);
        }
        else if (!final[v])
            pre[u]=min(pre[u], tin[v]);
        else if (flag[v])
        {
            ans2=ss;
            ans2.push_back(mp[{u, v}]);
            ok=1;
            break;
        }
    }
    if (ok)
        return;
    if (pre[u]==tin[u])
    {
        int okok=(s.back()!=u);
        if (okok && !firsttime)
            ans1=ss;
        cnt++;
        while (s.back()!=u)
        {
            scc[s.back()]=cnt;
            if (okok && !firsttime)
                flag[s.back()]=cnt;
            sz[cnt]++;
            s.pop_back();
        }
        scc[s.back()]=cnt;
        if (okok && !firsttime)
            flag[s.back()]=cnt;
        sz[cnt]++;
        s.pop_back();
        if (okok && !firsttime)
            firsttime=1;
    }
    final[u]=1;
}
void dfs2(int u)
{
    for (int v:adj[u])
    {
        if (v==target)
        {
            ans3.push_back(mp[{u, v}]);
            ok=1;
            break;
        }
        if (tin[v]<tin[u])
            continue;
        ans3.push_back(mp[{u, v}]);
        dfs2(v);
        if (ok)
            break;
        ans3.pop_back();
    }
}
void dfs3(int u)
{
    for (int v:adj[u])
    {
        if (scc[v]==target)
        {
            ans4.push_back(mp[{u, v}]);
            ok=1;
            break;
        }
        if (tin[v]<tin[u])
            continue;
        ans4.push_back(mp[{u, v}]);
        dfs3(v);
        if (ok)
            break;
        ans4.pop_back();
    }
}
void dfs4(int u)
{
    visited[u]=1;
    for (int v:adj[u])
    {
        if (visited[v])
            continue;
        int ind=lower_bound(ans3copy.begin(), ans3copy.end(), v)-ans3copy.begin();
        if (ind!=ans3copy.size() && ans3copy[ind]==v)
        {
            ans5.push_back(mp[{u, v}]);
            ok=1;
            break;
        }
        ans5.push_back(mp[{u, v}]);
        dfs4(v);
        if (ok)
            break;
        ans5.pop_back();
    }
}
variant<bool, vector<int> > find_journey(int n, int m, vector<int> u, vector<int> v)
{
    for (int i=0; i<m; i++)
    {
        adj[u[i]].push_back(v[i]);
        mp[{u[i], v[i]}]=i;
    }
    dfs(0);
    if (ok)
    {
        /*cout << "ans1: ";
        for (int i=0; i<ans1.size(); i++)
            cout << ans1[i].first << ' ' << ans1[i].second << ' ';
        cout << '\n';

        cout << "ans2: ";
        for (int i=0; i<ans2.size(); i++)
            cout << ans2[i].first << ' ' << ans2[i].second << ' ';
        cout << '\n';*/

        int ind=0;
        while (ind<min(ans1.size(), ans2.size()) && ans1[ind]==ans2[ind])
            ind++;
        for (int i=0; i<ans1.size(); i++)
            ans.push_back(ans1[i]);
        
        target=(ans1.empty()?0:v[ans1.back()]);
        ok=0;
        dfs2(target);

        /*cout << "ans3: ";
        for (int i=0; i<ans3.size(); i++)
            cout << ans3[i].first << ' ' << ans3[i].second << ' ';
        cout << '\n';*/

        for (int i=0; i<ans3.size(); i++)
            ans.push_back(ans3[i]);
        
        int sz1=ans1.size();
        for (int i=sz1-1; i>=ind; i--)
            ans.push_back(ans1[i]);
        
        for (int i=ind; i<ans2.size(); i++)
            ans.push_back(ans2[i]);
        
        int tmp=(ans2.empty()?0:v[ans2.back()]);
        for (int i=0; i<ans3.size(); i++)
            ans3copy.push_back(u[ans3[i]]);
        ans3copy.push_back(v[ans3.back()]);
        sort(ans3copy.begin(), ans3copy.end());
        ok=0;

        ind=lower_bound(ans3copy.begin(), ans3copy.end(), tmp)-ans3copy.begin();
        if (ind==ans3copy.size() || ans3copy[ind]!=tmp)
            dfs4(tmp);

        int sz5=ans5.size();
        for (int i=0; i<ans5.size(); i++)
            ans.push_back(ans5[i]);
        
        tmp=(ans5.empty()?tmp:v[ans5.back()]);
        
        for (int i=0; i<ans3.size(); i++)
        {
            if (v[ans3[i]]==tmp)
            {
                ind=i;
                break;
            }
        }
        int sz3=ans3.size();
        for (int i=ind; i>=0; i--)
            ans.push_back(ans3[i]);
        for (int i=sz3-1; i>ind; i--)
            ans.push_back(ans3[i]);
        
        for (int i=sz5-1; i>=0; i--)
            ans.push_back(ans5[i]);
        
        int sz2=ans2.size();
        for (int i=sz2-1; i>=0; i--)
            ans.push_back(ans2[i]);
        
        return ans;
    }
    for (int i=0; i<n; i++)
        flag[i]=0;
    int scc1=0, scc2=0;
    for (int i=1; i<=cnt; i++)
    {
        if (sz[i]>=2)
        {
            if (!scc1)
                scc1=i;
            else if (!scc2)
            {
                scc2=i;
                break;
            }
        }
    }
    if (!scc2)
        return (bool)0;
    
    target=scc1;
    ok=0;
    dfs3(0);
    ans11=ans4;
    ans4.clear();
    
    target=scc2;
    ok=0;
    dfs3(0);
    ans21=ans4;
    ans4.clear();

    target=(ans11.empty()?0:v[ans11.back()]);
    ok=0;
    dfs2(target);
    ans12=ans3;
    ans3.clear();

    target=(ans21.empty()?0:v[ans21.back()]);
    ok=0;
    dfs2(target);
    ans22=ans3;

    /*cout << "----------11:\n";

    for (int i=0; i<ans11.size(); i++)
        cout << u[ans11[i]] << ' ' << v[ans11[i]] << '\n';
    
cout << "----------12:\n";
    
    for (int i=0; i<ans12.size(); i++)
        cout << u[ans12[i]] << ' ' << v[ans12[i]] << '\n';
    
    cout << "----------21:\n";
    for (int i=0; i<ans21.size(); i++)
        cout << u[ans21[i]] << ' ' << v[ans21[i]] << '\n';
    
    cout << "----------22:\n";
    for (int i=0; i<ans22.size(); i++)
        cout << u[ans22[i]] << ' ' << v[ans22[i]] << '\n';*/

    int sz11=ans11.size(), sz12=ans12.size(), sz21=ans21.size(), sz22=ans22.size();

    int ind=0;
    while (ind<min(sz11, sz21) && ans11[ind]==ans21[ind])
        ind++;

    for (int i=0; i<sz11; i++)
        ans.push_back(ans11[i]);
    for (int i=0; i<sz12; i++)
        ans.push_back(ans12[i]);
    for (int i=sz11-1; i>=ind; i--)
        ans.push_back(ans11[i]);
    
    for (int i=ind; i<sz21; i++)
        ans.push_back(ans21[i]);
    for (int i=0; i<sz22; i++)
        ans.push_back(ans22[i]);
    for (int i=sz21-1; i>=ind; i--)
        ans.push_back(ans21[i]);
    
    reverse(ans12.begin(), ans12.end());
    reverse(ans22.begin(), ans22.end());

    for (int i=ind; i<sz11; i++)
        ans.push_back(ans11[i]);
    for (int i=0; i<sz12; i++)
        ans.push_back(ans12[i]);
    for (int i=sz11-1; i>=ind; i--)
        ans.push_back(ans11[i]);
    
    for (int i=ind; i<sz21; i++)
        ans.push_back(ans21[i]);
    for (int i=0; i<sz22; i++)
        ans.push_back(ans22[i]);
    for (int i=sz21-1; i>=0; i--)
        ans.push_back(ans21[i]);
    
    return ans;
}

Compilation message (stderr)

islands.cpp: In function 'void dfs4(int)':
islands.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         if (ind!=ans3copy.size() && ans3copy[ind]==v)
      |             ~~~^~~~~~~~~~~~~~~~~
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:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  141 |         while (ind<min(ans1.size(), ans2.size()) && ans1[ind]==ans2[ind])
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:143:24: 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<ans1.size(); i++)
      |                       ~^~~~~~~~~~~~
islands.cpp:155:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for (int i=0; i<ans3.size(); i++)
      |                       ~^~~~~~~~~~~~
islands.cpp:162:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for (int i=ind; i<ans2.size(); i++)
      |                         ~^~~~~~~~~~~~
islands.cpp:166:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         for (int i=0; i<ans3.size(); i++)
      |                       ~^~~~~~~~~~~~
islands.cpp:173:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         if (ind==ans3copy.size() || ans3copy[ind]!=tmp)
      |             ~~~^~~~~~~~~~~~~~~~~
islands.cpp:177:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |         for (int i=0; i<ans5.size(); i++)
      |                       ~^~~~~~~~~~~~
islands.cpp:182:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         for (int i=0; i<ans3.size(); i++)
      |                       ~^~~~~~~~~~~~

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