Submission #825772

#	Time	Username	Problem	Language	Result	Execution time	Memory
825772		LittleCube	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	36 ms	13468 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
  int K;
  vector<int> order, cc, vis, topo, dp;
  vector<vector<int>> scc;
  vector<pii> E[100000], R[100000];
  void dfs(int u)
  {
    vis[u] = 1;
    for (auto [v, i] : E[u])
      if (!vis[v])
        dfs(v);
    order.emplace_back(u);
  }
  void dfscc(int u, int r)
  {
    vis[u] = 1;
    cc[u] = r;
    scc[r].emplace_back(u);
    for (auto [v, i] : R[u])
      if (!vis[v])
        dfscc(v, r);
  }
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
  for (int i = 0; i < M; i++)
  {
    E[U[i]].emplace_back(pii(V[i], i));
    R[V[i]].emplace_back(pii(U[i], i));
  }
  vis.resize(N, 0);
  cc = vis;
  for (int i = 0; i < N; i++)
    if (!vis[i])
      dfs(i);
  for (int i = 0; i < N; i++)
    vis[i] = 0;
  reverse(order.begin(), order.end());
  for (int i : order)
    if (!vis[i])
    {
      topo.emplace_back(i);
      scc.emplace_back(vector<int>());
      dfscc(i, K++);
    }
  dp.resize(K, 0);
  for (int i = K - 1; i >= 0; i--)
  {
    if (scc[i].size() > 1)
      dp[i] = 1;
    for (auto j : scc[i])
      for (auto [k, _] : E[j])
        dp[i] |= dp[cc[k]];
  }
  int cnt = 0;
  for (auto [i, _] : E[0])
    if (dp[cc[i]])
      cnt++;
  if (cnt >= 2)
    return true;
  return false;
}

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