Submission #1079170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079170		NourWael	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	37 ms	12320 KiB

islands

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

int const mxN = 1e3+5;
vector<pair<int,int>> adj[mxN], adj2[mxN];
int n,m, cnt[mxN][mxN];
bool vis[mxN], poss[mxN];
vector<int> from[mxN];
bool flag = 0;

void dfs ( int i ) {
  for(auto it:adj[i]) {
    if(vis[it.first]) continue;
    vis[it.first] = 1;
    if(adj[it.first].size()>2) { flag = 1; return; }
    dfs(it.first);
  }
}

variant<bool,vector<int>> find_journey( int N, int M,vector<int> U, vector<int> V) {
  
  n = N, m = M;
  for(int i=0; i<m; i++) { adj[U[i]].push_back({V[i],i}), adj2[V[i]].push_back({U[i],i}); cnt[U[i]][V[i]]++; }
  
  for(auto it:adj[0]) {
    memset(vis,0,sizeof vis);
    vis[it.first] = 1; dfs(it.first);
    for(int i=1; i<n; i++) {
      if(vis[i]) from[i].push_back(it.first);
    }
  }

  bool f = 0;
  for(int i=1; i<n; i++) if(from[i].size()>1) f = 1;
  for(int i=1; i<n; i++) if(cnt[0][i]>1 ) f = 1;
  vector<int> v;
  if(adj[0].size()>1) return v;
  else {
   vis[0] = 1; dfs(0);
  }
  if(flag) return v;
  return false;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:35:8: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   35 |   bool f = 0;
      |        ^

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