제출 #1057601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057601		vjudge1	수천개의 섬 (IOI22_islands)	C++17	24 / 100	21 ms	8836 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100100];
vector<int>RES;
bitset<100100>vis,ons;
vector<int>stk;
void MKCYC(vector<int>v){
    for(auto i:v)
        RES.push_back(i);
    for(auto i:v)
        RES.push_back(i^1);
    reverse(v.begin(),v.end());
    for(auto i:v)
        RES.push_back(i);
    for(auto i:v)
        RES.push_back(i^1);
}
int dfs(int n){
    vis[n]=1;
    ons[n]=1;
    stk.push_back(n);
    for(auto[go,ind]:adj[n]){
        if(ons[go]){
            vector<int>v{ind};
            while(stk.back()!=go)
                stk.pop_back(),
                v.push_back(RES.back()),
                RES.pop_back();
            reverse(v.begin(),v.end());
            vector<int>stilon=RES;
            MKCYC(v);
            reverse(stilon.begin(),stilon.end());
            for(auto i:stilon)
                RES.push_back(i);
            return 1;
        }
        if(vis[go])continue;
        RES.push_back(ind);
        if(dfs(go)) {
            return 1;
        }
        RES.pop_back();
    }
    ons[n]=0;
    stk.pop_back();
    return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    for(int i=0;i<M;i+=2)
        adj[U[i]].push_back({V[i],i});
    if(dfs(0))
        return RES;
    return false;
}

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