Submission #1172980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172980		davele	Thousands Islands (IOI22_islands)	C++20	10 / 100	18 ms	4468 KiB

islands

#ifndef davele
#include "islands.h"
#endif // davele

#include <bits/stdc++.h>
#include <variant>
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;

int id[405][405];

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V){
    if (N==2){
        vector <int> f0, f1;
        int cnt = 0;
        for (int i=0; i<M; i++){
            if (U[i]==0) f0.pb(i);
            else f1.pb(i);
        }
        if ((int)f0.size()<=1) return false;
        if (f1.empty()) return false;
        vector <int> ret;
        ret.pb(f0[0]);
        ret.pb(f1[0]);
        ret.pb(f0[1]);
        ret.pb(f0[0]);
        ret.pb(f1[0]);
        ret.pb(f0[1]);
        return ret;
    }
    bool is2 = true;
    if (N>400) is2 = false;
    memset(id, -1, sizeof(id));
    if (M!=N*(N-1)) is2 = false;
    if (is2){
        memset(id, -1, sizeof(id));
        for (int i=0; i<M; i++) id[U[i]][V[i]] = i;
        for (int i=0; i<M; i++) for (int j=0; j<M; j++) 
            if (i!=j && id[i][j]==-1) is2 = false;
    }
    if (is2){
        int st = 0, en = 0;
        for (int i=0; i<M; i++) if (U[i]==0) st++;
        for (int i=0; i<M; i++) if (V[i]==0) en++;
        
        if (st<=1 || en==0) return false;
        //
        vector <int> ret;
        ret.pb(id[0][1]);
        ret.pb(id[1][0]);
        ret.pb(id[0][2]);
        ret.pb(id[2][0]);
        ret.pb(id[1][0]);
        ret.pb(id[0][1]);
        ret.pb(id[2][0]);
        ret.pb(id[0][2]);
        return ret;
    }
}

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:111:1: warning: control reaches end of non-void function [-Wreturn-type]
  111 | }
      | ^

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