Submission #628341

#	Time	Username	Problem	Language	Result	Execution time	Memory
628341		MarkBcc168	Thousands Islands (IOI22_islands)	C++17	0 / 100	29 ms	3028 KiB

islands

#include <bits/stdc++.h>
using namespace std;

int reverse_edge(int ind){
    if(ind % 2 == 0) return ind+1;
    else return ind-1;
}

std::variant<bool, std::vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v){
    //case 1; multiple edge through 0
    vector<int> e0(n,-1);
    int a=-1, b=-1;
    for(int i=0; i<m; ++i){
        if(u[i] == 0){
            if(e0[v[i]] != -1){
                a = e0[v[i]]; b = i; break;
            }
        }
    }
    return vector<int>{a, reverse_edge(a), b, reverse_edge(b), reverse_edge(a), a, reverse_edge(b), b};
    //case 2; do a simple cycle
    vector<pair<int,int>> adj[n];
    for(int i=0; i<m; i+=2){
        adj[u[i]].push_back(make_pair(v[i],i));
        adj[v[i]].push_back(make_pair(u[i],i+1));
    }
    //find cycle
    vector<int> prev(n,-1), st(1,0);
    vector<bool> vis(n, false);
    bool found = false;
    while(!st.empty()){
        int v = st[st.size()-1];
        st.pop_back();
        vis[v] = true;
        for(pair<int,int> p : adj[v]){
            int u = p.first;
            if(u==0 && prev[v]/2 != p.second/2){
                found = true; 
                prev[0] = p.second; 
                break;
            }
            if(vis[u]) continue;
            prev[u] = p.second;
            st.push_back(u);
        }
        if(found) break;
    }
    if(!found) return false;
    vector<int> cyc;
    int x = 0;
    do{
        cyc.push_back(prev[x]);
        x = u[prev[x]];
    }while(x != 0);
    reverse(cyc.begin(), cyc.end());

    //now print the journey
    vector<int> c;
    for(int e : cyc){
        c.push_back(e);
    }
    for(int e : cyc){
        c.push_back(reverse_edge(e));
    }
    reverse(cyc.begin(), cyc.end());
    for(int e : cyc){
        c.push_back(e);
    }
    for(int e : cyc){
        c.push_back(reverse_edge(e));
    }
    return c;
}

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