Submission #1037618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037618		sleepntsheep	Thousands Islands (IOI22_islands)	C++17	10 / 100	1097 ms	9328 KiB

islands

#include "islands.h"
#include<queue>
#include<cstring>
#include <variant>
#include <vector>
#include<set>
using namespace std;

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    vector<vector<int>> a(N);
    for (int i = 0; i < M; ++i)
        a[U[i]].push_back(i);

    int is_sub2 = N<=400;
    static int id[401][401];
    if(N<=400){
        memset(id, -1, sizeof id);
        for(int i=0;i<M;++i)id[U[i]][V[i]]=i;
        for(int i=0;i<N;++i)for(int j=i+1;j<N;++j)
            if(id[i][j]==-1 ||id[j][i]==-1)is_sub2=0;
    }
    if (N==2){
        if(a[0].size()>=2&&a[1].size()){
            int a1=a[0][0],a2=a[0][1],a3=a[1][0];
            return vector<int>{a1, a3, a2, a1, a3, a2};
        }
        return false;
    }else if(is_sub2){
        int a1=id[0][1],a2=id[1][0],a3=id[1][2],a4=id[2][1],a5=id[2][0],a6=id[0][2];
        return vector<int>{a1,a3,a5,a6,a4,a2,a5,a3,a1,a2,a4,a6};
    }else{
        vector<vector<int>>g(N);
        for (int i = 0; i < M; ++i) g[U[i]].push_back(V[i]);

        vector<vector<int>>d(N,vector<int>(N,1e9));
        vector<int>par(N),cyclike(N);

        for(int i=N-1;i>=0;--i){queue<int>q;d[i][i]=0;q.push(i);while(q.size()){int u=q.front();q.pop();for(int v:g[u])if(d[i][v]>d[i][u]+1)d[i][v]=d[i][u]+1,q.push(v),par[v]=u;}}

        for(int i=0;i<N;++i){
            vector<int>freq(N);
            //for(int v:g[i])if(1==freq[v]++){ cyclike[i]++;break; }
            for(int j=0;j<N;++j){ if(j!=i&&d[i][j]+d[j][i]<1e9){cyclike[i]++;break;} }
        }

        vector<vector<int>>T(N);
        for(int i=1;i<N;++i)T[par[i]].push_back(i);
        int cc=0;
        auto dfs=[&](auto&&dfs,int u)->void{
            if(cyclike[u]){++cc;return;}
            for(auto v:g[u])dfs(dfs,v);
        };
        if(cyclike[0]) return true;
        dfs(dfs,0);
        if(cc<2)return false;
        return true;
    }
}

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