Submission #814739

#	Time	Username	Problem	Language	Result	Execution time	Memory
814739		LIF	Thousands Islands (IOI22_islands)	C++17	0 / 100	33 ms	22800 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
int ind[300005];
int ph[1005][1005];
vector<int> vv[300005];
bool can[300005];
void dfs(int now,int fa)
{
  can[now] = true;
  for(int i=0;i<vv[now].size();i++)
  {
    int go = vv[now][i];
    if(can[go] == false)dfs(go,now);
  }
}
vector <int> temp; 
bool vis[30005];
int used[300005];
bool find_path(int now,int target)
{
  //for(int i=0;i<temp.size();i++)cout<<temp[i]<<" ";
 // cout<<now<<" "<<target<<endl;
  if(now == target)
  {
    temp.push_back(target);
    return true;
  }
  temp.push_back(now);
  bool flag = false;
  vis[now] = true;
  for(int i=0;i<vv[now].size();i++)
  {
    int go = vv[now][i];
    if(vis[go] == false)
    {
      if(find_path(go,target) == true)flag = true;
    }
  }
  if(flag == false)temp.pop_back();
  if(flag == true)used[now] = true;
  return flag;
}

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++)
  {
    vv[U[i]].push_back(V[i]);
    ph[U[i]][V[i]] = i;
    ind[V[i]]++;
  }
  dfs(0,-1);
  int target = -1;
  if(ind[0] >= 2)target = 0;
  for(int i=1;i<N;i++)
  {
     if(ind[i] >= 3 && can[i] == true)target = i; 
  } 
  if(target != -1)find_path(0,target);
  if(target == -1)return false;
  vector<int> last;
  for(int i=0;i<vv[target].size();i++)
  {
    int to = vv[target][i];
    if(used[to] == false)last.push_back(to);
    if(last.size() >= 2)break;
  }
  vector<int> all; 
  //step 1: 
  for(int i=0;i<temp.size()-1;i++)all.push_back(ph[temp[i]][temp[i+1]]);
  //step 2: 
  int l1 = last[0];
  int l2 = last[1];
  all.push_back(ph[target][l1]);
  all.push_back(ph[l1][target]);
  all.push_back(ph[target][l2]);
  all.push_back(ph[l2][target]);
  all.push_back(ph[l1][target]);
  all.push_back(ph[target][l1]);
  all.push_back(ph[l2][target]);
  all.push_back(ph[target][l2]);
 //step3:
  for(int i=0;i<temp.size()-1;i++)all.push_back(ph[temp[i]][temp[i+1]]);
  return all;

}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int, int)':
islands.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int i=0;i<vv[now].size();i++)
      |               ~^~~~~~~~~~~~~~~
islands.cpp: In function 'bool find_path(int, int)':
islands.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<vv[now].size();i++)
      |               ~^~~~~~~~~~~~~~~
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:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<vv[target].size();i++)
      |               ~^~~~~~~~~~~~~~~~~~
islands.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i=0;i<temp.size()-1;i++)all.push_back(ph[temp[i]][temp[i+1]]);
      |               ~^~~~~~~~~~~~~~
islands.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0;i<temp.size()-1;i++)all.push_back(ph[temp[i]][temp[i+1]]);
      |               ~^~~~~~~~~~~~~~

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