Submission #1244733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244733		sano	Thousands Islands (IOI22_islands)	C++20	0 / 100	1094 ms	4128 KiB

islands

//#include "insects.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#include <variant>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

int dfs(int s, vec<int>&c, vec<int>&r, vec<vec<pii>>&g, vec<bool>&bol, set<int>&je) {
    bol[s] = 1;
    je.insert(s);
    for (auto &i : g[s]) {
        if (je.find(i.ff) != je.end()) {
            c.push_back(i.ss);
            je.erase(s);
            return i.ff;
        }
        int x = dfs(i.ff, c, r, g, bol, je);
        if (x == -2) {
            r.push_back(i.ss);
            je.erase(s);
            return -2;
        }
        if (x != -1) {
            c.push_back(i.ss);
            je.erase(s);
            if (x == s) return -2;
            else return x;
        }
    }
    je.erase(s);
    return -1;
}

pair<vec<int>, vec<int>> cyc(vec<vec<pii>>&g, int s) {
    vec<int> c, r;
    set<int> je;
    vec<bool> bol(g.size(), 0);
    dfs(s, c, r, g, bol, je);
    return { c, r };
}

int opacna(int x) {
    if ((x % 2) == 0) {
        return x + 1;
    }
    return x - 1;
}

void otoc(vec<int>& x) {
    vec<int> y = x;
    x.clear();
    For(i, y.size()) {
        x.push_back(y[y.size() - 1 - i]);
    }
    return;
}

void dfs2(int x, vec<bool>& bol, vec<vec<pii>>& g) {
    bol[x] = 1;
    for (auto i : g[x]) {
        if (bol[i.ff]) continue;
        dfs2(i.ff, bol, g);
    }
    return;
}

variant<bool, vector<int>> find_journey(int n, int m, vec<int> u, vec<int> v) {
    vec<vec<pii>> g(n);
    vec<int> poc(n, 0);
    for (int i = 0; i < m; i+=2) {
        g[u[i]].push_back({ v[i], i });
    }
    vec<bool> bol(n);
    dfs2(0, bol, g);
    for (int i = 0; i < m; i+=2) {
        if (bol[u[i]] && bol[v[i]]) poc[v[i]]++;
    }
    vec<int> sp;
    For(i, n) {
        if (poc[i] == 0 && bol[i]) {
            sp.push_back(i);
        }
    }
    while (!sp.empty()) {
        int x = sp.back(); sp.pop_back();
        bol[x] = 0;
        for (auto i : g[x]) {
            poc[i.ff]--;
            if (poc[i.ff] == 0) {
                sp.push_back(i.ff);
            }
        }
    }
    bool ok = 0;
    For(i, n) {
        if (bol[i] == 1) {
            ok = 1;
        }
    }
    if (ok == 0) {
        return false;
    }
    vec<int> odp;
    pair<vec<int>, vec<int>> sracka = cyc(g, 0);
    vec<int> c = sracka.ff;
    vec<int> r = sracka.ss;
    if (c.size() == 0) {
        return false;
    }
    vec<int> c2;
    otoc(r);
    otoc(c);
    For(i, c.size()) {
        c2.push_back(opacna(c[c.size() - 1 - i]));
    }
    otoc(c2);
    for (auto i : r) {
        odp.push_back(i);
    }
    for (auto i : c) {
        odp.push_back(i);
    }
    for (auto i : c2) {
        odp.push_back(i);
    }
    otoc(c);
    for (auto i : c) {
        odp.push_back(i);
    }
    otoc(c2);
    for (auto i : c2) {
        odp.push_back(i);
    }
    otoc(r);
    for (auto i : r) {
        odp.push_back(i);
    }
    return odp;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m; cin >> n >> m;
    vec<int> u, v;
    For(i, m) {
        int a, b; cin >> a >> b;
        u.push_back(a);
        v.push_back(b);
    }
    variant<bool, vec<int>> odp = find_journey(n, m, u, v);
    if (holds_alternative<bool>(odp)) {
        cout << "odp is bool: " << get<bool>(odp) << endl;
    }
    else if (holds_alternative<vec<int>>(odp)) {
        cout << "odp is vector: ";
        for (int x : get<vec<int>>(odp)) {
            cout << x << ' ';
        }
        cout << endl;
    }
    return 0;
}*/

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