Submission #798134

#	Time	Username	Problem	Language	Result	Execution time	Memory
798134		MilosMilutinovic	Thousands Islands (IOI22_islands)	C++17	31 / 100	34 ms	10324 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector < pair <int, int> > g[N];
vector < pair <int, int> > G[N];
int conn[500][500], pp[N], par[N];
pair <int, int> go_up[N];
bool was[N], good;
vector <int> cyc;
void dfs_cyc(int x, int fa) {
  if (!cyc.empty()) return;
    was[x] = true;
  int cnt = 0;
    vector<int> ch;
    for (auto& p : G[x]) {
        int y = p.first;
        int id = p.second;
        if (id / 2 == fa / 2) continue;
        ch.push_back(id);
        if (was[y]) {
            int ver = x;
            while (false && ver != y) {
                cyc.push_back(go_up[ver].second);
                ver = go_up[ver].first;
            }
            //reverse(cyc.begin(), cyc.end());
         
          cnt++;
            continue;
        }
      cnt++;
        go_up[y] = {x, id};
        pp[y] = id;
        par[y] = x;
        dfs_cyc(y, id);
        if (!cyc.empty()) return;
    }
  if (cnt >= 2) {
    good = true;
    int v = x;
    vector<int> gg;
    while (v > 0) {
      gg.push_back(pp[v]);
      v = par[v];
    }
    reverse(gg.begin(), gg.end());
    for (int i : gg) cyc.push_back(i);
    cyc.push_back(ch[0]);
    cyc.push_back(ch[0] ^ 1);
    cyc.push_back(ch[1]);
    cyc.push_back(ch[1] ^ 1);
    cyc.push_back(ch[0] ^ 1);
    cyc.push_back(ch[0]);
    cyc.push_back(ch[1] ^ 1);
    cyc.push_back(ch[1]);
    reverse(gg.begin(), gg.end());
    for (int i : gg) cyc.push_back(i);
    return;
  }
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
 
    for (int i = 0; i < M; i++) {
        g[U[i]].emplace_back(V[i], i);
    }
 
    if (N == 2) {
        if (g[0].size() >= 2 && g[1].size() >= 1) {
            vector <int> ans;
            ans.push_back(g[0][0].second);
            ans.push_back(g[1][0].second);
            ans.push_back(g[0][1].second);
            ans.push_back(g[0][0].second);
            ans.push_back(g[1][0].second);
            ans.push_back(g[0][1].second);
            return ans;
        } else return false;
    }
 
    if (N <= 400) {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                conn[i][j] = -1;
        for (int i = 0; i < M; i++)
            conn[U[i]][V[i]] = i;
        bool sub2 = true;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (i != j && conn[i][j] == -1)
                    sub2 = false;
        if (sub2) {
            vector <int> ans;
 
            ans.push_back(conn[0][1]);
            ans.push_back(conn[1][2]);
            ans.push_back(conn[2][0]);
 
            ans.push_back(conn[0][2]);
            ans.push_back(conn[2][1]);
            ans.push_back(conn[1][0]);
 
            ans.push_back(conn[2][0]);
            ans.push_back(conn[1][2]);
            ans.push_back(conn[0][1]);
 
            ans.push_back(conn[1][0]);
            ans.push_back(conn[2][1]);
            ans.push_back(conn[0][2]);
 
            return ans;
        }
    }
 
    bool sub3 = (M % 2 == 0);
    for (int i = 0; i < M - 1; i += 2)
        sub3 = (sub3 & (U[i] == V[i + 1]) & (V[i] == U[i + 1]));
 
    if (sub3) {
        for (int i = 0; i < M; i += 2) {
            G[U[i]].emplace_back(V[i], i);
            G[V[i]].emplace_back(U[i], i + 1);
        }
        dfs_cyc(0, -3);
        if (!good) return false;
        return cyc;
    }
 
    assert(false);
 
    return false;
 
    if (N == 4) {
        return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
    }
    return false;
}

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