Submission #826372

#	Time	Username	Problem	Language	Result	Execution time	Memory
826372		alvingogo	Thousands Islands (IOI22_islands)	C++17	10 / 100	1062 ms	6720 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#define fs first
#define sc second
using namespace std;

vector<int> dep,fa;
vector<vector<pair<int,int> > > e;
void dfs(int r,int f){
    dep[r]=dep[f]+1;
    fa[r]=f;
    for(auto h:e[r]){
        if(dep[h.fs]<0){
            dfs(h.fs,r);
        }
    }
}
vector<int> dg[2];
vector<int> ss;
int dfs3(int r,int g,int k){
    for(auto h:e[r]){
        if(!ss[h.sc]){
            ss[h.sc]=1;
            dg[k].push_back(h.sc);
            if(h.fs==g){
                return 1;
            }
            if(dfs3(h.fs,g,k)){
                return 1;
            }
            ss[h.sc]=0;
            dg[k].pop_back();
        }
    }
    return 0;
}
int dfs2(int r){
    int a=dfs3(r,r,0);
    if(a){
        int b=dfs3(r,r,1);
        if(!b){
            for(auto h:dg[0]){
                ss[h]=0;
            }
            dg[0].clear();
        }
        return b;
    }
    return 0;
}
variant<bool, vector<int>> find_journey(
    int n, int m, vector<int> u, vector<int> v) {
    e.resize(n);
    ss.resize(m);
    fa.resize(n);
    dep.resize(n,-1);
    for(int i=0;i<m;i++){
        e[u[i]].push_back({v[i],i});
    }
    if(n==2){
        if(e[0].size()>=2 && e[1].size()>=1){
            vector<int> ans={e[0][0].sc,e[1][0].sc,e[0][1].sc,e[0][0].sc,e[1][0].sc,e[0][1].sc};
            return ans;
        }
        return false;
    }
    dfs(0,0);
    for(int i=0;i<n;i++){
        if(dep[i]>=0){
            if(dfs2(i)){
                vector<int> az,bz;
                for(int j=i;j!=0;j=fa[j]){
                    az.push_back(j);
                }
                for(int j=0;j!=i;){
                    for(auto h:e[j]){
                        if(h.fs==az.back()){
                            az.pop_back();
                            bz.push_back(h.sc);
                            j=h.fs;
                            break;
                        }
                    }
                }
                vector<int> ans;
                ans.insert(ans.end(),bz.begin(),bz.end());
                ans.insert(ans.end(),dg[0].begin(),dg[0].end());
                ans.insert(ans.end(),dg[1].begin(),dg[1].end());
                reverse(dg[0].begin(),dg[0].end());
                reverse(dg[1].begin(),dg[1].end());
                ans.insert(ans.end(),dg[0].begin(),dg[0].end());
                ans.insert(ans.end(),dg[1].begin(),dg[1].end());
                reverse(bz.begin(),bz.end());
                ans.insert(ans.end(),bz.begin(),bz.end());
                return ans;
            }
        }
    }
    return false;
}

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