Submission #1029043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029043		Mardonbekhazratov	Thousands Islands (IOI22_islands)	C++17	55 / 100	58 ms	16240 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]});
}

#define ff first
#define ss second

vector<vector<pair<int,int>>>adj;
vector<int>vis;

variant<bool,vector<int>>dfs(int x,int c){
    vis[x]=true;
    pair<int,int>y={-1,-1},z={-1,-1};
    for(auto j:adj[x]){
        // cout<<j.ss<<' ';
        if(j.ss==(c^1)) continue;
        if(y.ff==-1) y=j;
        else z=j;
    }
    if(z.ff!=-1) return vector<int>({y.ss,y.ss^1,z.ss,z.ss^1,y.ss^1,y.ss,z.ss^1,z.ss});
    for(auto [f,cc]:adj[x]){
        if(vis[f]) continue;
        variant<bool,vector<int>>res=dfs(f,cc);
        if(res.index()==0) continue;
        vector<int>sm=get<vector<int>>(res);
        vector<int>asn={cc};
        for(int h:sm) asn.push_back(h);
        asn.push_back(cc);
        return asn;
    }
    return false;
}

variant<bool,vector<int>>sub3(){
    adj.resize(n);
    for(int i=0;i<m;i++){
        adj[u[i]].push_back({v[i],i});
    }
    vis.assign(n,0);
    return dfs(0,-1);
}

vector<vector<int>>g;
vector<map<int,vector<int>>>mp;
vector<int>cycle,cf;
bool found;
int k;

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

vector<int>ans,ans1;

bool dfs2(int x){
    if(x==k) return true;
    vis[x]=true;
    for(int z:g[x]){
        if(vis[z]) continue;
        if(dfs2(z)){
            ans1.push_back(mp[x][z][0]);
            return true;
        }
    }
    return false;
}

variant<bool,vector<int>>sub4(){
    mp.resize(n);
    g.resize(n);
    for(int i=0;i<m;i++){
        g[u[i]].push_back(v[i]);
        mp[u[i]][v[i]].push_back(i);
    }
    cf.resize(n);
    vis.assign(n,0);
    found=false;
    dfs1(0,0);
    if(cycle.size()==0) return false;
    reverse(cycle.begin(),cycle.end());
    k=cycle[0];
    vis.assign(n,false);
    dfs2(0);
    reverse(ans1.begin(),ans1.end());
    for(int x:ans1) ans.push_back(x);
    // return vector<int>(0);
    cycle.push_back(k);
    for(int i=1;i<cycle.size();i++){
        ans.push_back(mp[cycle[i-1]][cycle[i]][0]);
    }
    for(int i=1;i<cycle.size();i++){
        ans.push_back(mp[cycle[i-1]][cycle[i]][1]);
    }
    for(int i=cycle.size()-1;i>0;i--){
        ans.push_back(mp[cycle[i-1]][cycle[i]][0]);
    }
    for(int i=cycle.size()-1;i>0;i--){
        ans.push_back(mp[cycle[i-1]][cycle[i]][1]);
    }
    reverse(ans1.begin(),ans1.end());
    for(int x:ans1) ans.push_back(x);
    return ans;
}

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();
    if(m==n*(n-1)) return sub2();
    if(u[0]!=u[1]) return sub3();
    return sub4();
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > sub4()':
islands.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=1;i<cycle.size();i++){
      |                 ~^~~~~~~~~~~~~
islands.cpp:131:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i=1;i<cycle.size();i++){
      |                 ~^~~~~~~~~~~~~

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