Submission #1235736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235736		Sir_Ahmed_Imran	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	20 ms	7496 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int dept[MAXN];
bool vis[MAXN];
vector<pii> a[MAXN];
vector<int> p, q, ans;

void dfs(int v, int i){
    vis[v] = 1;
    dept[v] = q.size();
    if(a[v].size() > 2 && ans.empty()){
        for(auto & j : q) ans.append(j);
        for(auto & [u, j] : a[v]){
            if((i ^ j) < 2) continue;
            p.append(j);
        }
        for(auto & j : p){
            ans.append(j);
            ans.append(j ^ 1);
        }
        for(auto & j : p){
            ans.append(j ^ 1);
            ans.append(j);
        }
        for(int j = q.size(); j > 0; j--)
            ans.append(q[j - 1]);
    } 
    for(auto & [u, j] : a[v]){
        if((i ^ j) < 2) continue;
        if(!vis[u]){
            q.append(j);
            dfs(u, j);
            q.pop_back();
        }
        else if(ans.empty()){
            q.append(j);
            for(int k = dept[u]; k < q.size(); k++)
                p.append(q[k]);
            for(auto & k : q)
                ans.append(k);
            reverse(all(p));
            for(auto & k : p)
                ans.append(k ^ 1);
            for(auto & k : p)
                ans.append(k);
            reverse(all(p));
            for(auto & k : p)
                ans.append(k ^ 1);
            for(int k = dept[u]; k > 0; k--)
                ans.append(q[k - 1]);
        }
    }
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v){
    for(int i = 0; i < m; i++)
        a[u[i]].append({v[i], i});
    if(a[0].size() > 1){
        for(auto & [u, j] : a[0])
            p.append(j);
        for(auto & j : p){
            ans.append(j);
            ans.append(j ^ 1);
        }
        for(auto & j : p){
            ans.append(j ^ 1);
            ans.append(j);
        }
    }
    if(ans.empty()) 
        return false;
    return ans;
}

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