Submission #760588

#	Time	Username	Problem	Language	Result	Execution time	Memory
760588		resting	Thousands Islands (IOI22_islands)	C++17	100 / 100	167 ms	35008 KiB

islands

#pragma once
 
#include <variant>
#include <bits/stdc++.h>
using namespace std;
 
#define MX 200000
 
bool dead[MX]{};
multiset<pair<int,int>> adj[MX];
vector<pair<int,int>> rev[MX];
 
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    //we should delete dead ends! just bc its fun!
    for (int i = 0; i < M; i++) {
        adj[U[i]].insert({ V[i], i });
        rev[V[i]].push_back({ U[i], i });
    }
    vector<int> del;
    for (int i = 0; i < N; i++) {
        if (!adj[i].size()) del.push_back(i);
    }
 
    auto machine = [&]() {
        while (del.size()) {
            int i = del.back(); del.pop_back();
            if (dead[i]) continue;
            dead[i] = 1;
            for (auto& x : rev[i]) {
                adj[x.first].erase({ i, x.second });
                if (!adj[x.first].size()) del.push_back(x.first);
            }
        }
    };
    machine();
 
    int i = 0;
 
    vector<int> initial_path;
    while (1) {
        if (dead[i]) return false;
        if (adj[i].size() >= 2) break;
        int t = i;
        initial_path.push_back(adj[i].begin()->second);
        i = adj[i].begin()->first;
        del.push_back(t);
        machine();
    }
 
    //35%
    auto [a, pa] = *adj[i].begin();
    auto [b, pb] = *adj[i].rbegin();
    //find the loops of a and b
    bool vis[MX] = {}; vis[i] = 1;
    vector<int> la = {pa};
    while (!vis[a]) {
        vis[a] = 1;
        la.push_back(adj[a].begin()->second);
        a = adj[a].begin()->first;
    }
    auto lpa = la.begin();
    if (a != i) lpa = find(la.begin(), la.end(), adj[a].begin()->second);
 
 
    //document a's cycle
    bool visa[MX] = {};
    while (!visa[a]) {
        visa[a] = 1;
        a = adj[a].begin()->first;
    }
 
    
    bool vis2[MX] = {}; vis2[i] = 1;
    vector<int> lb = { pb };
    while (!visa[b] && !vis2[b]) {
        vis2[b] = 1;
        lb.push_back(adj[b].begin()->second);
        b = adj[b].begin()->first;
    }
    auto lpb = lb.begin();
    if (visa[b]) lpb = find(la.begin(), la.end(), adj[b].begin()->second);
    else if (b != i) lpb = find(lb.begin(), lb.end(), adj[b].begin()->second);
 
 
    // build the answer 
    std::vector<int>::iterator owo;
    vector<int> ans;
    ans.insert(ans.end(), initial_path.begin(), initial_path.end());
 
    if (visa[b]) {
        //case 1: same loop
        
        //loop a
        ans.insert(ans.end(), la.begin(), la.end());
        vector<int> t = { la.begin(), lpa };
        ans.insert(ans.end(), t.rbegin(), t.rend());
 
        //loop b
        ans.insert(ans.end(), lb.begin(), lb.end());
        t = { lpb, la.end() };
        t.insert(t.end(), lpa, lpb);
        ans.insert(ans.end(), t.rbegin(), t.rend());
        ans.insert(ans.end(), lb.rbegin(), lb.rend());
 
    }
    else {
        //case 2: diff loop
 
        //loop a
        ans.insert(ans.end(), la.begin(), la.end());
        vector<int> t = { la.begin(), lpa };
        ans.insert(ans.end(), t.rbegin(), t.rend());
 
        //loop b
        ans.insert(ans.end(), lb.begin(), lb.end());
        t = { lb.begin(), lpb };
        ans.insert(ans.end(), t.rbegin(), t.rend());
 
 
        //loop a
        ans.insert(ans.end(), la.begin(), lpa);
        t = { lpa, la.end() };
        ans.insert(ans.end(), t.rbegin(), t.rend());
        t = { la.begin(), lpa };
        ans.insert(ans.end(), t.rbegin(), t.rend());
 
        //loop b
        ans.insert(ans.end(), lb.begin(), lpb);
        t = { lpb, lb.end() };
        ans.insert(ans.end(), t.rbegin(), t.rend());
        t = { lb.begin(), lpb };
        ans.insert(ans.end(), t.rbegin(), t.rend());
    }
    
    ans.insert(ans.end(), initial_path.rbegin(), initial_path.rend());
    
    return ans;
}
 
//int main() {
//    auto x = find_journey(2, 3, { 0, 0, 1}, { 1, 1, 0 });
//    for (auto& i : get<vector<int>>(x)) cout << i << endl;
//}

Compilation message (stderr)

islands.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |      ^~~~

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