Submission #764411

#	Time	Username	Problem	Language	Result	Execution time	Memory
764411		raysh07	Thousands Islands (IOI22_islands)	C++17	24 / 100	74 ms	7160 KiB

islands

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

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

void dfs1(int u){
    v1[u] = true;
    ok[u] = path;
    for (auto [v, i] : adj[u]){
        if (!v1[v]){
            dep[v] = dep[u] + 1;
            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;
    int ong = 0;
    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);
    
    for (auto x : ans){
        if (ong != bruh[x].first) assert(false);
        ong = bruh[x].second;
        swap(bruh[x].first, bruh[x].second);
    }
    assert(ong == 0);
    
    return ans;
}

bool comp(int x, int y) {
    return dep[x] < dep[y];
}

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++){
        bruh[i] = {u[i], v[i]};
    }
    for (int i = 0; i < m; i += 2){
        adj[u[i]].push_back({v[i], i});
    }
    
    dfs1(0);
    vector <int> perm;
    for (int i = 0; i < n; i++) perm.push_back(i);
    sort(perm.begin(), perm.end(), comp);
    
    for (auto i : perm){
        if (v1[i]){
            curr = i;
            path.clear();
            //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: 24 / 24
• Subtask 5: 0 / 45