Submission #837479

#	Time	Username	Problem	Language	Result	Execution time	Memory
837479		fatemetmhr	Thousands Islands (IOI22_islands)	C++17	17.35 / 100	110 ms	26664 KiB

islands

// Be name khoda //


#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   x.begin(), x.end()
#define pb       push_back
#define mp       make_pair
#define fi       first
#define se       second

typedef long long ll;

const int mod   = 1e9 + 9;
const int maxn5 = 2e5 + 10;

vector <pair<int, int>> adj[maxn5];
bool mark[maxn5];
map <int, int> have[maxn5];
int mt[maxn5];

std::variant<bool, std::vector<int>> find_journey(
    int n, int m, std::vector<int> u, std::vector<int> v) {
    if(n == 2){
        vector <int> cnt[2], ret;
        for(int i = 0; i < m; i++){
            cnt[u[i]].pb(i);

        }
        if(int(cnt[0].size()) < 2 || int(cnt[1].size()) < 1)
            return false;
        int a = cnt[0][0], b = cnt[0][1], c = cnt[1][0];
        return vector <int> ({a, c, b, a, c, b});
    }
    for(int i = 0; i < m; i++){
        adj[u[i]].pb({v[i], i});
        have[u[i]][v[i]] = i;
        if(have[v[i]].find(u[i]) != have[v[i]].end()){
            mt[have[v[i]][u[i]]] = i;
            mt[i] = have[v[i]][u[i]];
        }
    }
    vector <int> ret;
    int x = 0;
    while(true){
        mark[x] = true;
        int cnt = 0;
        for(auto [u, id] : adj[x]) if(!mark[u])
            cnt++;
        if(!cnt)
            return false;
        if(cnt == 1){
            for(auto [u, id] : adj[x]) if(!mark[u]){
                ret.pb(id);
                x = u;
                break;
            }
            continue;
        }
        vector <int> tmp = ret, have;
        reverse(all(tmp));

        for(auto [u, id] : adj[x]) if(!mark[u])
            have.pb(id);

        int a = have[0], b = have[1];
        ret.pb(a);
        ret.pb(mt[a]);
        ret.pb(b);
        ret.pb(mt[b]);

        ret.pb(mt[a]);
        ret.pb(a);
        ret.pb(mt[b]);
        ret.pb(b);

        for(auto u : tmp)
            ret.pb(u);
        return ret;
    }
    return false;
}

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