Submission #1211858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211858		serkanrashid	Thousands Islands (IOI22_islands)	C++20	1.75 / 100	1038 ms	1070192 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

struct edge
{
    int ver,num;
    edge(){};
    edge(int vi, int ni)
    {
        ver = vi;
        num = ni;
    }
};

const int MAXN = 2e5+5;
int n,m,u[MAXN],v[MAXN];

int idx,ans[MAXN];
vector<edge>g[MAXN],o[MAXN];///obraten

vector<int>v0[MAXN],v1[MAXN];

void solve1()
{
    for(edge nb : g[0])
    {
        v0[nb.ver].push_back(nb.num);
    }
    for(edge nb : o[0])
    {
        v1[nb.ver].push_back(nb.num);
    }

    for(int i = 1; i < n; i++)
    {
        if((int)v0[i].size() >= 2 && (int)v1[i].size() >= 1)
        {
            int u1 = v0[i][0];
            int u2 = v0[i][1];
            int v = v1[i][0];
            ans[idx] = u1;
            ans[idx+1] = v;
            ans[idx+2] = u2;
            ans[idx+3] = u1;
            ans[idx+4] = v;
            ans[idx+5] = u2;
            idx += 6;
            break;
        }
    }
}

struct PAR
{
    int p,num;
};

int used[MAXN];
PAR par[MAXN];
int cikul,num_e;

void dfs(int beg)
{
    used[beg] = 1;
    for(edge nb : g[beg])
    {
        if(cikul != -1) break;
        if(used[nb.ver])
        {
            if(nb.ver == 0) continue;
            if(cikul != -1) continue;
            cikul = beg;
            num_e = nb.num;
            break;
        }
        else
        {
            par[nb.ver] = {beg,nb.num};
            dfs(nb.ver);
        }
    }
}

vector<int> is_cycle()
{
    for(int i = 0; i < n; i++) used[i] = 0;
    for(int i = 0; i < n; i++) par[i] = {0,0};

    cikul = -1;
    par[0] = {0,-1};
    dfs(0);


    vector<int>sp;
    if(cikul == -1) return sp;


    sp.push_back(num_e);
    int kraj = v[num_e];

    int x = cikul;
    while(x != kraj)
    {
        sp.push_back(par[x].num);
        x = par[x].p;
    }
    reverse(sp.begin(),sp.end());

    vector<int>put;
    ///x = kraj;
    while(x != 0)
    {
        put.push_back(par[x].num);
        x = par[x].p;
    }
    reverse(put.begin(),put.end());

    vector<int>ans;
    for(int h : put) ans.push_back(h);
    for(int h : sp) ans.push_back(h);
    for(int i = (int)put.size() - 1; i >= 0; i--) ans.push_back(put[i]);

    for(int h : put) ans.push_back(h);
    for(int i = (int)sp.size() - 1; i >= 0; i--) ans.push_back(sp[i]);
    for(int i = (int)put.size() - 1; i >= 0; i--) ans.push_back(put[i]);
    return ans;
}

variant <bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V)
{
    n = N;
    m = M;
    for(int i = 0; i < M; i++)
    {
        u[i] = U[i];
        v[i] = V[i];
        g[u[i]].push_back({v[i],i});
        o[v[i]].push_back({u[i],i});
    }
    solve1();
    if(idx != 0)
    {
        vector<int>res;
        res.resize(idx);
        for(int i = 0; i < idx; i++) res[i] = ans[i];
        return res;
    }

    vector<int> res = is_cycle();
    if((int)res.size()) return res;

    return false;
}

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