Submission #1073178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073178		beaconmc	Thousands Islands (IOI22_islands)	C++17	24 / 100	148 ms	32380 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

const ll maxn = 100005;
set<int> edges[maxn];
bool visited[maxn];
bool realvisited[maxn];

bool flag = 0;

vector<int> stacks;

vector<int> cycle;

map<vector<int>, int> idk;
map<vector<int>, int> idk2;

void dfs(ll a){
    if (flag) return;
    visited[a] = 1;
    realvisited[a] = 1;
    stacks.push_back(a);

    for (auto&i : edges[a]){
        if (flag) return;

        if (realvisited[i]){

            flag = 1;

            

            
            FORNEG(j,stacks.size()-1, -1){
                if (stacks[j]==i) break;
                else cycle.push_back(stacks[j]);
                stacks.pop_back();

            }
            cycle.push_back(i);
            stacks.pop_back();
            reverse(cycle.begin(), cycle.end());
            return;

        }
        else{
            if (!visited[i]) visited[i] = 1, dfs(i);

        }
    }
    if (flag) return;
    stacks.pop_back();
    realvisited[a] = 0;
}

map<vector<int>, vector<int>> crazy;
set<vector<int>> visiteds;

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    stacks.clear();
    cycle.clear();

    flag = 0;
    FOR(i,0,maxn) visited[i] = 0;
    FOR(i,0,maxn) edges[i].clear();

    FOR(i,0,M){
        edges[U[i]].insert(V[i]);
        if (idk.count({U[i], V[i]})) idk2[{U[i], V[i]}] = i;
        else idk[{U[i], V[i]}] = i;
    }
    dfs(0);
    if (flag==0) return false;




    vector<int> journey;



    for (auto&i : stacks) journey.push_back(i);

    for (auto&i : cycle) journey.push_back(i);
    for (auto&i : cycle) journey.push_back(i);
    journey.push_back(cycle[0]);
    journey.push_back(-1);
    journey.push_back(cycle[0]);
    reverse(cycle.begin(), cycle.end());
    for (auto&i : cycle) journey.push_back(i);
    for (auto&i : cycle) journey.push_back(i);
    reverse(stacks.begin(), stacks.end());
    for (auto&i : stacks) journey.push_back(i);






    vector<int> ans;

    bool idkman = false;
    FOR(i,1,journey.size()){
        if (journey[i-1] == -1) continue;
        if (journey[i]==-1){
            for (auto&i : crazy){
                reverse(crazy[i.first].begin(), crazy[i.first].end());
            }
            idkman = true;
            continue;
        }

        if (idkman==0){
            if (visiteds.count({journey[i-1], journey[i]})){
                ans.push_back(idk2[{journey[i-1], journey[i]}]);
                crazy[{journey[i],journey[i-1]}].push_back(idk2[{journey[i-1], journey[i]}]);
            }else{
                visiteds.insert({journey[i-1], journey[i]});
                ans.push_back(idk[{journey[i-1], journey[i]}]);
                crazy[{journey[i],journey[i-1]}].push_back(idk[{journey[i-1], journey[i]}]);
            }
        }else{

            ans.push_back(crazy[{journey[i-1], journey[i]}][crazy[{journey[i-1], journey[i]}].size()-1]);
            crazy[{journey[i-1], journey[i]}].pop_back();
        }



    }

    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:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  109 |     FOR(i,1,journey.size()){
      |         ~~~~~~~~~~~~~~~~~~       
islands.cpp:109:5: note: in expansion of macro 'FOR'
  109 |     FOR(i,1,journey.size()){
      |     ^~~

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