Submission #1028895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028895		Mardonbekhazratov	Thousands Islands (IOI22_islands)	C++17	10 / 100	70 ms	12376 KiB

islands

#include "islands.h"

#include <variant>
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <map>

using namespace std;

int n,m;
vector<int>u,v;

variant<bool,vector<int>>sub1(){
    vector<int>c1,c2;
    for(int i=0;i<m;i++){
        if(u[i]==0) c1.push_back(i);
        else c2.push_back(i);
    }
    if(c1.size()<2 || c2.size()<1) return false;
    return vector<int>({c1[0],c2[0],c1[1],c1[0],c2[0],c1[1]});
}

vector<int>sub2(){
    vector<vector<int>>a(3,vector<int>(3));
    for(int i=0;i<m;i++){
        if(u[i]<3 && v[i]<3) a[u[i]][v[i]]=i;
    }
    return vector<int>({a[0][1],a[1][0],a[0][2],a[2][1],a[0][1],a[1][0],a[2][1],a[0][2]});
}

vector<vector<int>>adj;
vector<int>vis,cf,cycle;
bool found;

void dfs(int x,int p){
    if(found) return;
    vis[x]=1;
    cf[x]=p;
    for(int z:adj[x]){
        if(z==p || vis[z]==2 || found) continue;
        if(vis[z]==1){
            while(x!=z){
                cycle.push_back(x);
                x=cf[x];
            }
            cycle.push_back(0);
            found=true;
            return;
        }
        if(vis[z]==1) continue;
        dfs(z,x);
    }
    vis[x]=2;
}

variant<bool,vector<int>>sub3(){
    adj.resize(n);
    vector<map<int,int>>b(n);
    for(int i=0;i<m;i++){
        adj[u[i]].push_back(v[i]);
        b[u[i]][v[i]]=i;
    } 
    if(adj[0].size()>1) return vector<int>({b[0][adj[0][0]],b[adj[0][0]][0],b[0][adj[0][1]],b[adj[0][1]][0],b[adj[0][0]][0],b[0][adj[0][0]],b[adj[0][1]][0],b[0][adj[0][1]]});
    vis.assign(n,0);
    found=false;
    cf.resize(n);
    dfs(0,0);
    vector<int>ans;
    if(cycle.size()<3) return false;
    return vector<int>(0);
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    tie(n,m,u,v)=tie(N,M,U,V);
    if(n==2) return sub1();
    return sub3();
}


/*
4 8
0 1
1 0
1 2
2 1
2 3
3 2
0 3
3 0
*/

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