Submission #1076925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076925		Ignut	Thousands Islands (IOI22_islands)	C++17	24 / 100	58 ms	14168 KiB

islands

/* Ignut
started: 11.08.2024
now: 26.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int MAXN = 1e5 + 123;
int n;
 
vector<pair<int, int>> g[MAXN];
int used[MAXN];

vector<int> order;
  
bool ans = false;

int startCycle = -1;

void dfs(int v) {
    if (ans) return;
    used[v] = 1;
    order.push_back(v);
    // cout << "go " << v << '\n';
    for (auto [to, e] : g[v]) {
        if (ans) return;
        if (used[to] == 2)
            continue;
        if (used[to] == 1) {
            // cout << "find cycle to " << to << '\n';
            ans = true;
            startCycle = to;
            return;
        }
        if (ans) return;
        dfs(to);
    }
    if (ans) return;
    used[v] = 2;
    // cout << "delete " << v << '\n';
    order.pop_back();
}
 
int cnt[MAXN] = {};
 
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N;
    map<pair<int, int>, int> idx;
    for (int i = 0; i < M; i += 2) {
        g[U[i]].push_back({V[i], i});
        idx[{U[i], V[i]}] = i;
    }
    dfs(0);
    if (!ans) return false;

    vector<int> path, cycle;
    bool onC = false;
    for (int v : order) {
        if (v == startCycle) onC = true;
        if (onC) cycle.push_back(v);
        else path.push_back(v);
    }

    path.push_back(startCycle);
    // for (int v : path) cout << v << ' ';
    // cout << '\n';

    vector<int> res;
    for (int i = 1; i < path.size(); i ++)
        res.push_back(idx[{path[i - 1], path[i]}]);

    vector<int> ci;
    for (int i = 0; i < cycle.size(); i ++) {
        int u = cycle[i], v = cycle[(i + 1) % cycle.size()];
        ci.push_back(idx[{u, v}]);
    }
    for (int e : ci) res.push_back(e);
    for (int e : ci) res.push_back(e + 1);
    reverse(ci.begin(), ci.end());
    for (int e : ci) res.push_back(e);
    for (int e : ci) res.push_back(e + 1);

    for (int i = int(path.size()) - 1; i > 0; i --) {
        res.push_back(idx[{path[i - 1], path[i]}]);
    }

    return res;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 1; i < path.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
islands.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0; i < cycle.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~

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