제출 #764358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764358		raysh07	수천개의 섬 (IOI22_islands)	C++17	8.40 / 100	125 ms	7248 KiB

islands

#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1001;
vector <pair<int, int>> adj[N];
bool v1[N], vis[N];
int curr;
int n;
vector <int> path, ok[N], ok1;

void dfs(int u){
    vis[u] = true;
    
    for (auto [v, i] : adj[u]){
        path.push_back(i);
        if (v == curr && ok1.size() == 0){
            ok1 = path;
        } else if (!vis[v]){
            dfs(v);
        } 
        path.pop_back();
    }
}

void dfs1(int u){
    v1[u] = true;
    ok[u] = path;
    for (auto [v, i] : adj[u]){
        if (!v1[v]){
            path.push_back(i);
            dfs1(v);
            path.pop_back();
        }
    }
}

void add(vector <int> &a, vector <int> b, bool rev, int xo = 0){
    if (rev) reverse(b.begin(), b.end());
    for (auto x : b) a.push_back(x ^ xo);
}

vector <int> get(int i){
    vector <int> ans;
    add(ans, ok[i], false);
    add(ans, ok1, false);
    add(ans, ok1, false, 1);
    add(ans, ok1, true);
    add(ans, ok1, true, 1);
    add(ans, ok[i], true);
    return ans;
}

variant<bool, vector<int>> find_journey(int nn, int m, vector<int> u, vector<int> v) {
    n = nn;
    for (int i = 0; i < m; i += 2){
        adj[u[i]].push_back({v[i], i});
    }
    
    dfs1(0);
    
    for (int i = 0; i < n; i++){
        if (v1[i]){
            curr = i;
            //look for cycle starting and ending at i 
            //good if someone can reach curr 
            
            for (int j = 0; j < n; j++) vis[j] = false;
            dfs(i);
            if (ok1.size()) return get(i);
        }
    }
    return false;
}

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