Submission #777569

#	Time	Username	Problem	Language	Result	Execution time	Memory
777569		alexander707070	Thousands Islands (IOI22_islands)	C++17	0 / 100	7 ms	10708 KiB

islands

#include<bits/stdc++.h>
#include <variant>
#define MAXN 200007
using namespace std;

int n,m;
vector< pair<int,int> > v[MAXN];
vector<int> path,sol;
int ind[MAXN];

void euler(int x,int start,int cnt,int e){
    if(x==start and cnt>0){
        path.push_back(e); return;
    }

    bool fr=true;
    for(int i=ind[x];i<v[x].size();i++){
        ind[x]++;

        if(fr){
            fr=false; euler(v[x][i].first,start,cnt+1,v[x][i].second);
        }else{
            euler(v[x][i].first,x,1,v[x][i].second);
        }

        i=max(i,ind[x]-1);
    }

    path.push_back(e);
}

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++){
        U[i]++; V[i]++;
        v[U[i]].push_back({V[i],i});
    }

    euler(1,1,0,-1);

    path.pop_back();
    reverse(path.begin(),path.end());

    if(path.size()!=m)cout<<1/0;

    for(int i=0;i<m;i++){
        if(path[i]==-1)cout<<1/0;
        sol.push_back(path[i]);
    }
    for(int i=m-1;i>=0;i--){
        sol.push_back(path[i]);
    }
    
    if(sol.empty())return false;
    return sol;
}

/*
int main(){
    find_journey(6, 7, {0,1,2,2,3,4,5}, {1,2,3,5,4,2,0});
}
*/

Compilation message (stderr)

islands.cpp: In function 'void euler(int, int, int, int)':
islands.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=ind[x];i<v[x].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:44:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(path.size()!=m)cout<<1/0;
      |        ~~~~~~~~~~~^~~
islands.cpp:44:30: warning: division by zero [-Wdiv-by-zero]
   44 |     if(path.size()!=m)cout<<1/0;
      |                             ~^~
islands.cpp:47:31: warning: division by zero [-Wdiv-by-zero]
   47 |         if(path[i]==-1)cout<<1/0;
      |                              ~^~

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