Submission #1084573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084573		SamueleVid	Thousands Islands (IOI22_islands)	C++17	10 / 100	50 ms	32696 KiB

islands

#include <bits/stdc++.h>
using namespace std;

// constexpr int MAXN = 1e5 + 5;
constexpr int MAXN = 1e3 + 5;
constexpr int MAXM = 2e5 + 5;

// vector<pair<int, int>> adj[MAXN]; // nodo, barca
vector<int> adj[MAXN][MAXN];
bool v[MAXN];
bool auto_ciclo[MAXN];
vector<int> barche;
vector<int> barche_res;
vector<int> nodi;
int N;
bool fatto = false;

variant<bool, vector<int>> n_two(int N, int M, vector<int> U, vector<int> V) {
    vector<int> el_primo;
    vector<int> el_secondo;
    for (int i = 0; i < M; i ++) {
        if (U[i] == 0) el_primo.push_back(i);
        if (U[i] == 1) el_secondo.push_back(i);
    }

    if (el_primo.size() >= 2 && el_secondo.size() >= 1) {
        int a = el_primo[0];
        int b = el_secondo[0];
        int c = el_primo[1];
        vector<int> res = {a, b, c, a, b, c};
        return res;
    }

    return false;
}

variant<bool, vector<int>> subtask_two(int N, int M, vector<int> U, vector<int> V) {
    int a, b, c, d, e, f;
    for (int i = 0; i < M; i ++) {
        if (U[i] == 0 && V[i] == 1) a = i;
        if (U[i] == 1 && V[i] == 0) b = i;
        if (U[i] == 1 && V[i] == 2) c = i;
        if (U[i] == 2 && V[i] == 1) d = i;
        if (U[i] == 2 && V[i] == 0) e = i;
        if (U[i] == 0 && V[i] == 2) f = i;
    }

    vector<int> res = {a, c, e, f, d, b, e, c, a, b, d, f};
    return res;
}



void dfs(int u) {
    if (fatto) return;
    // cout << "sono a u " << u << '\n';
    nodi.push_back(u);
    if (auto_ciclo[u]) fatto = true;
    if (v[u]) {
        // cout << "trovato ciclo !!" << '\n';
        // minchia ora comincia il bello
        int primo_u = -1;
        for (int i = 0; i < nodi.size(); i ++) {
            if (nodi[i] == u) {
                primo_u = i;
                break;
            }
        }
        // assert(primo_u != -1);
        // cout << "primo u " << u << " -> " << primo_u << '\n';

        // for (int i = 0; i < N; i ++) {
            // for (int j = 0; j < N; j ++) {
                // cout << "Barche da " << i << " a " << j << " : ";
                // for (auto x : adj[i][j]) cout << (char)(x + 'A') << " ";
                // cout << '\n';
            // }
        // }

        // cout << "Nodi : " << '\n';
        // for (auto x : nodi) cout << x << " ";
        // cout << '\n';
        // cout << "piroetta due volte" << '\n';
        int prec = u;
        vector<int> to_add_one, to_add_two;
        // cout << "- prima volta" << '\n';
        for (int i = nodi.size() - 2; i >= primo_u; i --) {
            // cout << "i, nodo : " << i << " " << nodi[i] << '\n';
            if (adj[prec][nodi[i]].size() == 0) exit(-1);
            int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
            // cout << "visito " << nodi[i] << " con barca " << (char)(barca + 'A') << '\n';
            adj[nodi[i]][prec].push_back(barca);
            
            to_add_two.push_back(barca);
            prec = nodi[i];
        }

        // cout << "- seconda volta" << '\n';
        for (int i = nodi.size() - 2; i >= primo_u; i --) {
            // cout << "i, nodo : " << i << " " << nodi[i] << '\n';
            int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
            // cout << "visito " << nodi[i] << " con barca " << (char)(barca + 'A') << '\n';
            adj[nodi[i]][prec].push_back(barca);
            
            to_add_one.push_back(barca);
            prec = nodi[i];
        }
        for (auto x : to_add_one) barche.push_back(x);
        for (auto x : to_add_two) barche.push_back(x);



        // cout << "--- e ora piroetta normale " << '\n';
        for (int i = primo_u + 1; i < nodi.size(); i ++) {
            // cout << "i, nodo : " << i << " " << nodi[i] << '\n';
            int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
            // cout << "visito " << nodi[i] << " con barca " << (char)(barca + 'A') << '\n';
            adj[nodi[i]][prec].push_back(barca);
            
            barche.push_back(barca);
            prec = nodi[i];
        }
        
        // cout << " e torno indietro " << '\n'; 

        for (int i = primo_u - 1; i >= 0; i --) {
            // cout << "vedo i, nodo : " << i << " " << nodi[i] << '\n';
            int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
            adj[nodi[i]][prec].push_back(barca);

            // cout << "visito " << i << " con barca " << (char)(barca + 'A') << '\n';
            
            barche.push_back(barca);
            prec = nodi[i];
        }
        barche_res = barche;

        fatto = true;
        return;
    }
    if (fatto) return;
    v[u] = 1;

    for (int i = 0; i < N; i ++) {
        if (nodi.size() >= 2 && nodi[nodi.size() - 2] == i) continue;
        if (adj[u][i].empty()) continue;

        int barca = adj[u][i].back(); adj[u][i].pop_back();
        adj[i][u].push_back(barca);

        // cout << "vado da " << i << " e prendo barca " << (char)(barca + 'A') << '\n';

        barche.push_back(barca);
        dfs(i);
        if (fatto) return;
        barche.pop_back();

        adj[i][u].pop_back();
        adj[u][i].push_back(barca);
    }
    if (fatto) return;

    v[u] = 0;
    nodi.pop_back();
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    :: N = N;
    if (N <= 2) return n_two(N, M, U, V);
    // if (N <= 400) return subtask_two(N, M, U, V);

    fill(v, v + MAXN, 0);
    fill(auto_ciclo, auto_ciclo + MAXN, 0);
    for (int i = 0; i < MAXN; i ++) {
        for (int j = 0; j < MAXN; j ++) adj[i][j] = vector<int>();
    }

    vector<pair<int, int>> robi;
    for (int i = 0; i < M; i ++) {
        adj[U[i]][V[i]].push_back(i);
        robi.push_back({U[i], V[i]});
    }
    sort(robi.begin(), robi.end());
    for (int i = 1; i < M; i ++) {
        if (robi[i] == robi[i - 1]) {
            auto [u, v] = robi[i];
            auto_ciclo[u] = 1;
        }
    }

    // for (int i = 0; i < MAXN; i ++) {
    //     for (int j = 0; j < MAXN; j ++) if (adj[i][j].size() > 1) exit(-1);
    // }

    dfs(0);
    if (fatto) return barche_res;
    return false;
}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int)':
islands.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0; i < nodi.size(); i ++) {
      |                         ~~^~~~~~~~~~~~~
islands.cpp:114:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for (int i = primo_u + 1; i < nodi.size(); i ++) {
      |                                   ~~^~~~~~~~~~~~~
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > subtask_two(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:48:58: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     vector<int> res = {a, c, e, f, d, b, e, c, a, b, d, f};
      |                                                          ^
islands.cpp:48:58: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
islands.cpp:48:58: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
islands.cpp:48:58: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
islands.cpp:48:58: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
islands.cpp:48:58: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

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