Submission #787640

#	Time	Username	Problem	Language	Result	Execution time	Memory
787640		alexander707070	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	40 ms	23644 KiB

islands

#include<bits/stdc++.h>
#include <variant>
#define MAXN 200007
using namespace std;
 
int n,m,root,banned;
vector< pair<int,int> > v[MAXN];
vector<int> path,sol,z,ans;
int ind[MAXN];
 
void euler(int x,int e){
    for(int i=ind[x];i<v[x].size();i++){
        ind[x]++;
        if(v[x][i].first==banned)continue;

        euler(v[x][i].first,v[x][i].second);
        i=max(i,ind[x]-1);
    }
 
    path.push_back(e);
}

int dfs(int x,int p){
    if(v[x].size()>2 or (p==0 and v[x].size()>1)){
        banned=p; return x;
    }

    for(int i=0;i<v[x].size();i++){
        if(v[x][i].first!=p){
            z.push_back(v[x][i].second);
            return dfs(v[x][i].first,x);
        }
    }

    return -1;
}
 
variant< vector<int> , bool > 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});
    }

    root=dfs(1,0);
    if(root==-1){
        return sol;
        return false;
    }

    for(int i:z)sol.push_back(i);
 
    euler(root,-1);
 
    path.pop_back();
    reverse(path.begin(),path.end());

    for(int i=0;i<path.size();i++){
        sol.push_back(path[i]);
    }
 
    for(int i=1;i<=n;i++){
        v[i].clear(); ind[i]=0;
    }
    path.clear();
 
    for(int i=0;i<m;i++){
        v[V[i]].push_back({U[i],i});
    }
 
    euler(root,-1);
 
    path.pop_back();
    reverse(path.begin(),path.end());
    
    for(int i=0;i<path.size();i++){
        sol.push_back(path[i]);
    }

    for(int i=z.size()-1;i>=0;i--){
        sol.push_back(z[i]);
    }
 
    if(sol.empty())return false;

    return sol;
}
 
/*
int main(){
    ans=find_journey(3, 4, {0,1,1,2}, {1,0,2,1});
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
*/

Compilation message (stderr)

islands.cpp: In function 'void euler(int, int)':
islands.cpp:12: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]
   12 |     for(int i=ind[x];i<v[x].size();i++){
      |                      ~^~~~~~~~~~~~
islands.cpp: In function 'int dfs(int, int)':
islands.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
islands.cpp: In function 'std::variant<std::vector<int, std::allocator<int> >, bool> find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~
islands.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~

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