Submission #1239850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239850		MarwenElarbi	Thousands Islands (IOI22_islands)	C++17	26 / 100	19 ms	5192 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,int>> adj[1005];
bool vis[1005];
bool test=false;
vector<int> ans;
bool dfs(int x,int p,int boat){
    vis[x]=true;
    if(boat!=-1) ans.push_back(boat);
    if(adj[x].size()>=3){
        int a=-1,b=-1,c=-1,d=-1;
        for(auto u : adj[x]){
            if(u.fi==p) continue;
            if(a==-1) {
                a=u.se;
                for(auto i : adj[u.fi]) if(i.fi==x) c=i.se;
            }
            else if(b==-1) {
                b=u.se;
                for(auto i : adj[u.fi]) if(i.fi==x&&i.se!=c) d=i.se;
            }
            else break;
        }
        ans.push_back(a);
        ans.push_back(c);
        ans.push_back(b);
        ans.push_back(d);
        ans.push_back(c);
        ans.push_back(a);
        ans.push_back(d);
        ans.push_back(b);
        if(boat!=-1) ans.push_back(boat);
        return true;
    }
    bool test=false;
    for(auto u:adj[x]){
        if(vis[u.fi]) continue;
        if(dfs(u.fi,x,u.se)){
            test=true;
            break;
        }
    }
    if(boat==-1) return test;
    if(!test) ans.pop_back();
    else ans.push_back(boat);
    return test;
}
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    for (int i = 0; i < M; ++i)
    {
        adj[U[i]].push_back({V[i],i});
    }
    if(adj[0].size()>=2){
        int a = adj[0][0].se;
        int b = adj[0][1].se;
        int c;
        int d;
        for(auto u : adj[adj[0][0].fi]) if(u.fi==0) c=u.se;
        for(auto u : adj[adj[0][1].fi]) if(u.fi==0&&u.se!=c) d=u.se;
        return vector<int>({a,c,b,d,c,a,d,b});
    }
    if(dfs(0,-1,-1)) return ans;
    return false;
}

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