Submission #1239820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239820		MarwenElarbi	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	17 ms	4168 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> adj[1005];
bool vis[1005];
bool test=false;
vector<int> ans;
bool dfs(int x,int p){
    vis[x]=true;
    ans.push_back(x);
    if(adj[x].size()>=3){
        int a=-1,b=-1;
        for(auto u : adj[x]){
            if(u==p) continue;
            if(a==-1) a=u;
            else if(b==-1) b=u;
            else break;
        }
        ans.push_back(a);
        ans.push_back(x);
        ans.push_back(b);
        ans.push_back(x);
        ans.push_back(a);
        ans.push_back(x);
        ans.push_back(b);
        ans.push_back(x);
        return true;
    }
    bool test=false;
    for(auto u:adj[x]){
        if(vis[u]) continue;
        if(dfs(u,x)){
            test=true;
            break;
        }
    }
    if(!test) ans.pop_back();
    else ans.push_back(x);
    return test;
}
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    for (int i = 0; i < M; ++i)
    {
        adj[U[i]].push_back(V[i]);
    }
    if(adj[0].size()>=2){
        return vector<int>({0,adj[0][0],0,adj[0][1],0,adj[0][0],0,adj[0][1],0});
    }
    if(dfs(0,-1)) return ans;
    return false;
}

/*int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> U(M), V(M);
  for (int i = 0; i < M; ++i) {
    assert(2 == scanf("%d %d", &U[i], &V[i]));
  }

  std::variant<bool, std::vector<int>> result = find_journey(N, M, U, V);
  if (result.index() == 0) {
    printf("0\n");
    if (std::get<bool>(result)) {
      printf("1\n");
    } else {
      printf("0\n");
    }
  } else {
    printf("1\n");
    std::vector<int> &canoes = std::get<std::vector<int>>(result);
    printf("%d\n", static_cast<int>(canoes.size()));
    for (int i = 0; i < static_cast<int>(canoes.size()); ++i) {
      if (i > 0) {
        printf(" ");
      }
      printf("%d", canoes[i]);
    }
    printf("\n");
  }
  return 0;
}*/

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