Submission #939240

#	Time	Username	Problem	Language	Result	Execution time	Memory
939240		irmuun	Thousands Islands (IOI22_islands)	C++17	0 / 100	1116 ms	1171484 KiB

islands

#include<bits/stdc++.h>
#include "islands.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

variant<bool,vector<int>>find_journey(int n,int m,vector<int>u,vector<int>v){
    bool ok=false;
    vector<int>ans,road;
    vector<pair<int,int>>adj[n];
    for(int i=0;i<m;i+=2){
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
    }
    int cur=0,par=-1;
    while(true){
        int x=0,y=1;
        if(par==-1){
            if(adj[cur].size()>=2){
                ans.pb(adj[cur][0].ss);
                ans.pb(adj[cur][0].ss+1);
                ans.pb(adj[cur][1].ss);
                ans.pb(adj[cur][1].ss+1);
                ans.pb(adj[cur][0].ss+1);
                ans.pb(adj[cur][0].ss);
                ans.pb(adj[cur][1].ss+1);
                ans.pb(adj[cur][1].ss);
            }
            if(adj[cur].size()==0) return false;
            ans.pb(adj[cur][0].ss);
            road.pb(adj[cur][0].ss);
            par=cur;
            cur=adj[cur][0].ff;
        }
        else{
            int i=0,j=1;
            if(adj[cur].size()>=3){
                if(adj[cur][0].ff==par) i=1,j=2;
                else if(adj[cur][1].ff==par) j=2;
                ans.pb(adj[cur][i].ss);
                ans.pb(adj[cur][i].ss+1);
                ans.pb(adj[cur][j].ss);
                ans.pb(adj[cur][j].ss+1);
                ans.pb(adj[cur][i].ss+1);
                ans.pb(adj[cur][i].ss);
                ans.pb(adj[cur][j].ss+1);
                ans.pb(adj[cur][j].ss);
            }
            if(adj[cur].size()==1) return false;
            if(adj[cur][0].ff==par){
                ans.pb(adj[cur][1].ss);
                road.pb(adj[cur][1].ss);
                par=cur;
                cur=adj[cur][1].ff;
            }
            else{
                ans.pb(adj[cur][0].ss);
                road.pb(adj[cur][0].ss);
                par=cur;
                cur=adj[cur][0].ff;
            }
        }
    }
    for(int i=(int)road.size()-1;i>=0;i--){
        ans.pb(road[i]+1);
    }
    return ans;
}

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:23:13: warning: unused variable 'x' [-Wunused-variable]
   23 |         int x=0,y=1;
      |             ^
islands.cpp:23:17: warning: unused variable 'y' [-Wunused-variable]
   23 |         int x=0,y=1;
      |                 ^
islands.cpp:14:10: warning: unused variable 'ok' [-Wunused-variable]
   14 |     bool ok=false;
      |          ^~

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