Submission #1024791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024791		Wansur	Thousands Islands (IOI22_islands)	C++17	8.40 / 100	100 ms	117444 KiB

islands

#include <bits/stdc++.h>
#include <variant>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;
const int mod = 1e9 + 2022;

map<int, int> a[maxn];
vector<int> g[maxn];
int used[maxn];
vector<int> cyc, ord, ver, pref;
int n, m;

void dfs(int v){
    used[v] = 1;
    ver.push_back(v);
    for(int to:g[v]){
        if(used[to] == 1){
            cyc = ord;
            cyc.push_back(a[v][to]);
            for(int i=0;i<ver.size();i++){
                if(ver[i] == to){
                    break;
                }
                pref.push_back(cyc[i]);
            }
        }
        if(!used[to]){
            ord.push_back(a[v][to]);
            dfs(to);
            ord.pop_back();
        }
    }
    used[v] = 2;
    ver.pop_back();
}

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+=2){
        a[u[i]][v[i]] = i;
        g[u[i]].push_back(v[i]);
    }
    dfs(0);
    if(cyc.size() == 0){
        return false;
    }
    vector<int> ans = pref;
    reverse(cyc.begin(), cyc.end());
    for(int i=0;i<pref.size() && cyc.size();i++){
        cyc.pop_back();
    }
    reverse(cyc.begin(), cyc.end());
    for(int x:cyc){
        ans.push_back(x);
    }
    for(int x:cyc){
        ans.push_back(x+1);
    }
    reverse(cyc.begin(), cyc.end());
    for(int x:cyc){
        ans.push_back(x);
    }
    for(int x:cyc){
        ans.push_back(x+1);
    }
    reverse(pref.begin(), pref.end());
    for(int x:pref){
        ans.push_back(x);
    }
    return ans;
}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int)':
islands.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             for(int i=0;i<ver.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:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<pref.size() && cyc.size();i++){
      |                 ~^~~~~~~~~~~~

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