Submission #1241167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241167		MarwenElarbi	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	178 ms	31756 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 1e5+5;
multiset<int> adj[nax];
multiset<int> revadj[nax];
int outdeg[nax];
bool vis[nax];
bool nabba[nax];
bool test=false;
void dfs(int x){
  if(vis[x]) return;
  vis[x]=true;
  for(auto u: adj[x]) dfs(u);
}
void dfs1(int x){
  //cout <<x<<endl;
  if(nabba[x]) return;
  if(outdeg[x]>1) return;
  nabba[x]=true;
  if(outdeg[x]==1){
    for(auto u:revadj[x]){
      adj[u].erase(adj[u].count(x));
      outdeg[u]--;
    }
  }
  for(auto u:adj[x]) dfs1(u);
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
  int n = N;
  int m = M;
  for(int i = 0;i < m ; i++) 
  {
    outdeg[U[i]]++;
    adj[U[i]].insert(V[i]);
    revadj[V[i]].insert(U[i]);
  }
  queue<int> q;
  for(int i = 0;i < n;i++) if(outdeg[i]==0) q.push(i);
  while(!q.empty()){
    int x = q.front();
    q.pop();
    for(auto u : revadj[x]){
      adj[u].erase(adj[u].count(x));
      outdeg[u]--;
      if(outdeg[u]==0) q.push(u);
    }
  }
  dfs(0);
  dfs1(0);
  for(int i = 0 ;i < n; i++) if(outdeg[i]>=2&&vis[i]&&!nabba[i]) test=true;
  return test;
}

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