Submission #1073458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073458		jerzyk	Thousands Islands (IOI22_islands)	C++17	100 / 100	289 ms	139804 KiB

islands

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;

vector<int> U, V;
bool del[N];

bool vis[N], stay[N];

set<pair<int, int>> ed[N];
multiset<int> red[N];
vector<int> cur, pth, zb1, zb2;
int wch[N];

bool DFS(int v)
{
    vis[v] = true;
    //cerr << v << "\n";
    for(set<pair<int, int>>::iterator it = ed[v].begin(); it != ed[v].end(); ++it)
    {
        if(vis[(*it).st])
        {
            cur.pb((*it).nd);
            return true;
        }
        if(DFS((*it).st))
        {
            cur.pb((*it).nd);
            return true;
        }
    }
    return false;
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> XU, vector<int> XV)
{
    vector<int> ans;
    queue<int> q;
    U = XU; V = XV;
    int v = 0;
    for(int i = 0; i < m; ++i)
    {
        ed[U[i]].insert(make_pair(V[i], i));
        red[V[i]].insert(U[i]);
        ++wch[U[i]];
    }
    for(int i = 0; i < n; ++i)
        if(wch[i] == 0) q.push(i);
    //cerr << v << " " << wch[v] << "\n";
    if(wch[v] == 0) return false;
    while(wch[v] == 1)
    {
        del[v] = true;
        pth.pb((*ed[v].begin()).nd);
        for(multiset<int>::iterator it = red[v].begin(); it != red[v].end(); ++it)
        {
            --wch[*it];
            ed[*it].erase(ed[*it].lower_bound(make_pair(v, 0)));
            if(wch[*it] == 0)
                q.push(*it);
        }
        v = (*ed[v].begin()).st;
    }
    //cerr << "xd\n";
    while(q.size() > 0)
    {
        if(wch[v] == 0) return false;
        int u = q.front(); q.pop();
        if(del[u]) continue;
        del[u] = true;
        //cerr << "del " << u << "\n";
        for(multiset<int>::iterator it = red[u].begin(); it != red[u].end(); ++it)
        {
            --wch[*it];
            //cerr << "ed " << *it << "\n";
            ed[*it].erase(ed[*it].lower_bound(make_pair(u, 0)));
            if(wch[*it] == 0)
                q.push(*it);
        }
        if(wch[v] == 0) return false;
        while(wch[v] == 1)
        {
            del[v] = true;
            //cerr << "gov " << v << "\n";
            for(multiset<int>::iterator it = red[v].begin(); it != red[v].end(); ++it)
            {
                --wch[*it];
                ed[*it].erase(ed[*it].lower_bound(make_pair(v, 0)));
                if(wch[*it] == 0)
                    q.push(*it);
            }
            pth.pb((*ed[v].begin()).nd);
            v = (*ed[v].begin()).st;
        }
    }
    //cerr << "xd\n";
    //cerr << v << "\n";
    if(del[v] || wch[v] <= 1) return false;
    for(int i = 0; i < n; ++i) ed[i].clear();
    for(int i = 0; i < m; ++i)
        if(!del[V[i]] && !del[U[i]])
            ed[U[i]].insert(make_pair(V[i], i));
    DFS(v);
    reverse(cur.begin(), cur.end());
    //cout << "Cur1\n";
    //for(int i = 0; i < (int)cur.size(); ++i)
        //cout << cur[i] << " ";
    //cout << "\n";
    zb1 = cur;
    ed[U[zb1[0]]].erase(make_pair(V[zb1[0]], zb1[0]));
    cur.clear();
    DFS(v);
    reverse(cur.begin(), cur.end());
    //cout << "Cur2\n";
    //for(int i = 0; i < (int)cur.size(); ++i)
        //cout << cur[i] << " ";
    //cout << "\n";
    for(int i = 0; i < n; ++i) ed[i].clear();
    zb2 = cur;
    cur.clear();
    for(int i = 0; i < (int)zb1.size(); ++i)
    {
        int j = zb1[i];
        stay[j] = true;
        //ed[U[j]].insert(make_pair(V[j], j));
    }
    for(int i = 0; i < (int)zb2.size(); ++i)
        stay[zb2[i]] = true;
    for(int i = 0; i < m; ++i)
        if(!del[V[i]] && !del[U[i]] && stay[i])
            ed[U[i]].insert(make_pair(V[i], i));
    int lst = -1, cnt = 0, beg = v;
    cur = pth;
    while(true)
    {
        //cerr << "xd " << v << " " << beg << "\n";
        if(v == beg) ++cnt;
        if(cnt == 13) break;
        for(set<pair<int, int>>::iterator it = ed[v].begin(); it != ed[v].end(); ++it)
            if((*it).nd != lst)
            {
                int ne = (*it).st, num = (*it).nd;
                ed[v].erase(it);
                ed[ne].insert(make_pair(v, num));
                lst = num;
                cur.pb(num);
                v = ne;
                break;
            }
    }
    for(int i = pth.size() - 1; i >= 0; --i)
        cur.pb(pth[i]);

    return cur;
}

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