Submission #1205049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205049		HappyCapybara	Thousands Islands (IOI22_islands)	C++20	1.75 / 100	20 ms	8264 KiB

islands

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

vector<int> p, c, t, tl;
vector<vector<int>> g;

void dfs(int cur, int par){
  if (!c.empty()) return;
  if (p[cur] != -1) return;
  if (tl[cur] != -1){
    c.push_back(cur);
    c.push_back(tl[cur]);
    while (cur != 0){
      t.push_back(cur);
      cur = p[cur];
    }
    t.push_back(cur);
    reverse(t.begin(), t.end());
    return;
  }
  p[cur] = par;
  for (int next : g[cur]){
    if (next == par) continue;
    if (p[next] != -1){
      while (cur != next && cur != 0){
        c.push_back(cur);
        cur = p[cur];
      }
      c.push_back(cur);
      while (cur != 0){
        t.push_back(cur);
        cur = p[cur];
      }
      t.push_back(cur);
      reverse(c.begin(), c.end());
      reverse(t.begin(), t.end());
      return;
    }
    dfs(next, cur);
    if (!c.empty()) return;
  }
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
  g.resize(N);
  vector<vector<int>> v(N, vector<int>(N, -1));
  tl.resize(N, -1);
  for (int i=0; i<M; i+=2){
    g[U[i]].push_back(V[i]);
    g[V[i]].push_back(U[i]);
    if (v[U[i]][V[i]] == -1) v[U[i]][V[i]] = i;
    else {
      tl[U[i]] = V[i];
      tl[V[i]] = U[i];
    }
    v[V[i]][U[i]] = i+1;
  }
  p.resize(N, -1);
  dfs(0, 0);
  if (c.empty()) return false;
  return true;
  /*for (int x : t) cout << x << " ";
  cout << endl;
  for (int x : c) cout << x << " ";
  cout << endl;*/
  vector<int> res;
  for (int i=0; i<t.size()-1; i++) res.push_back(v[t[i]][t[i+1]]);
  if (c.size() == 2){
    res.push_back(v[c[0]][c[1]]);
    res.push_back(v[c[0]][c[1]]^1);
    res.push_back(v[c[1]][c[0]]^1);
    res.push_back(v[c[0]][c[1]]);
    res.push_back(v[c[0]][c[1]]^1);
    res.push_back(v[c[1]][c[0]]^1);
  }
  else {
    for (int i=0; i<c.size(); i++) res.push_back(v[c[i]][c[(i+1)%c.size()]]);
    for (int i=c.size(); i>=1; i--) res.push_back(v[c[i%c.size()]][c[i-1]]);
    for (int i=c.size(); i>=1; i--) res.push_back(v[c[i-1]][c[i%c.size()]]);
    for (int i=0; i<c.size(); i++) res.push_back(v[c[(i+1)%c.size()]][c[i]]);
  }
  for (int i=(int)t.size()-1; i>=1; i--) res.push_back(v[t[i-1]][t[i]]);
  return res;
}

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