Submission #1072654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072654		jerzyk	Thousands Islands (IOI22_islands)	C++17	55 / 100	37 ms	65172 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], kloc[N];

bool vis[N];
int wys[N];
vector<pair<int, int>> ed[N];
vector<int> red[N];
int wch[N];
vector<int> pth, cur, bd = {-1};
int gdz[N];

void DoDel(int n)
{
    int v;
    queue<int> q;
    for(int i = 0; i < n; ++i)
    {
        wch[i] = ed[i].size();
        if(wch[i] == 0) q.push(i);
    }
    while((int)q.size() > 0)
    {
        v = q.front(); q.pop();
        del[v] = true;
        for(int i = 0; i < (int)red[v].size(); ++i)
        {
            --wch[red[v][i]];
            if(wch[red[v][i]] == 0) q.push(red[v][i]);
        }
    }
}

void MakeG(int n, int m)
{
    for(int i = 0; i < n; ++i)
        {ed[i].clear(); red[i].clear();}
    for(int i = 0; i < m; ++i)
    {
        int a = U[i], b = V[i];
        if(del[a] || del[b]) continue;
        //if(rev[i]) swap(a, b);
        ed[a].pb(make_pair(b, i));
        red[b].pb(a);
    }
}

bool DFS(int v, int av)
{
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(ed[v][i].nd == av || vis[ed[v][i].nd]) continue;
        if(wys[ed[v][i].st] != 0)
        {
            cur.pb(ed[v][i].nd);
            return true;
        }
        wys[ed[v][i].st] = wys[v] + 1;
        if(DFS(ed[v][i].st, av))
        {
            cur.pb(ed[v][i].nd);
            return true;
        }
    }
    return false;
}

pair<vector<int>, vector<int>> Find(int v, int n, int av)
{
    //cerr << "xd\n";
    vector<int> ans, a1, a2;
    bool abc;
    for(int i = 0; i < n; ++i) wys[i] = 0;
    wys[v] = 1;
    abc = DFS(v, av);
    if(!abc)
        return make_pair(bd, bd);
    reverse(cur.begin(), cur.end());
    int x = min(wys[U[cur.back()]], wys[V[cur.back()]]);
    ans = cur;
    //cerr << "find: " << v << " " << x << " " << av << "\n";
    //for(int i = 0; i < (int)cur.size(); ++i)
        //cout << cur[i] << " ";
    //cout << "\n";
    cur.clear();
    for(int i = 0; i <= x - 2; ++i)
        a1.pb(ans[i]);
    for(int i = x - 1; i < (int)ans.size(); ++i)
        a2.pb(ans[i]);
    //cerr << "xd\n";
    return make_pair(a1, a2);
}

vector<int> Mrg1(vector<int> p1, vector<int> c1, vector<int> p2, vector<int> c2)
{
    //cerr << "Mrg1\n";
    vector<int> ans;
    for(int i = 0; i < (int)p1.size(); ++i)
        ans.pb(p1[i]);
    for(int i = 0; i < (int)c1.size(); ++i)
        ans.pb(c1[i]);
    for(int i = p1.size() - 1; i >= 0; --i)
        ans.pb(p1[i]);

    for(int i = 0; i < (int)p2.size(); ++i)
        ans.pb(p2[i]);
    for(int i = 0; i < (int)c2.size(); ++i)
        ans.pb(c2[i]);
    for(int i = p2.size() - 1; i >= 0; --i)
        ans.pb(p2[i]);

    for(int i = 0; i < (int)p1.size(); ++i)
        ans.pb(p1[i]);
    for(int i = c1.size() - 1; i >= 0; --i)
        ans.pb(c1[i]);
    for(int i = p1.size() - 1; i >= 0; --i)
        ans.pb(p1[i]);

    for(int i = 0; i < (int)p2.size(); ++i)
        ans.pb(p2[i]);
    for(int i = c2.size() - 1; i >= 0; --i)
        ans.pb(c2[i]);
    for(int i = p2.size() - 1; i >= 0; --i)
        ans.pb(p2[i]);
    return ans;
}

vector<int> Mrg3(vector<int> p1, vector<int> c1, vector<int> p2, vector<int> c2)
{
    //cerr << "Mrg1\n";
    vector<int> ans;
    for(int i = 0; i < (int)p1.size(); ++i)
        ans.pb(p1[i]);
    for(int i = 0; i < (int)c1.size(); ++i)
        ans.pb(c1[i]);
    for(int i = p1.size() - 1; i >= 0; --i)
        ans.pb(p1[i]);

    for(int i = 0; i < (int)p2.size(); ++i)
        ans.pb(p2[i]);
    for(int i = c2.size() - 1; i >= 0; --i)
        ans.pb(c2[i]);
    for(int i = p2.size() - 1; i >= 0; --i)
        ans.pb(p2[i]);

    return ans;
}

bool Check(vector<int> a, vector<int> b)
{
    if(a.size() != b.size()) return false;

    pair<int, int> m1 = make_pair(N, N), m2 = make_pair(N, N);
    int l, r;
    for(int i = 0; i < (int)a.size(); ++i)
        m1 = min(m1, make_pair(a[i], i));
    for(int i = 0; i < (int)b.size(); ++i)
        m2 = min(m2, make_pair(b[i], i));
    l = m1.nd; r = m2.nd;
    for(int i = 0; i < (int)a.size(); ++i)
    {
        if(a[l] != b[r]) return false;
        ++l; ++r;
        l %= (int)a.size();
        r %= (int)b.size();
    }
    return true;
}

vector<int> DoC(int v, int n, int k)
{
    for(int i = 0; i < k; ++i) gdz[i] = -1;

    pair<vector<int>, vector<int>> xd;
    vector<int> p1, p2, c1, c2;
    vector<int> a1, a2, b1, b2, m;

    vector<int> ans;

    xd = Find(v, n, -1);
    p1 = xd.st; c1 = xd.nd;
    if((int)p1.size() > 0 && p1[0] == -1) return bd;
    int av = -1;
    if((int)p1.size() > 0) av = p1[0];
    else av = c1[0];
    xd = Find(v, n, av);
    p2 = xd.st; c2 = xd.nd;
    if((int)p2.size() > 0 && p2[0] == -1) return bd;
    if(Check(c1, c2))
        return Mrg3(p1, c1, p2, c2);
    int l = -1, r = -1;
    for(int i = 0; i < (int)c2.size(); ++i)
        gdz[c2[i]] = i;
    for(int i = 0; i < (int)c1.size(); ++i)
        if(gdz[c1[i]] != -1)
        {
            l = i; r = gdz[c1[i]]; break;
        }
    //cout << "LR: " << l << " " << r << "\n";
    if(l == -1)
        return Mrg1(p1, c1, p2, c2);
    for(int i = 0; i < l; ++i)
        a1.pb(c1[i]);
    for(int i = 0; i < r; ++i)
        b1.pb(c2[i]);
    while(c1[l] == c2[r] && l < (int)c1.size() && r < (int)c2.size())
    {
        m.pb(c1[l]);
        ++l; ++r;
    }
    for(int i = l; i < (int)c1.size(); ++i)
        a2.pb(c1[i]);

    for(int i = 0; i < (int)p1.size(); ++i)
        ans.pb(p1[i]);
    for(int i = 0; i < (int)c1.size(); ++i)
        ans.pb(c1[i]);
    for(int i = p1.size() - 1; i >= 0; --i)
        ans.pb(p1[i]);
    //cerr << "xd\n";
    for(int i = 0; i < (int)p2.size(); ++i)
        ans.pb(p2[i]);
    for(int i = 0; i < (int)b1.size(); ++i)
        ans.pb(b1[i]);
    for(int i = a1.size() - 1; i >= 0; --i)
        ans.pb(a1[i]);
    for(int i = a2.size() - 1; i >= 0; --i)
        ans.pb(a2[i]);
    for(int i = m.size() - 1; i >= 0; --i)
        ans.pb(m[i]);
    for(int i = b1.size() - 1; i >= 0; --i)
        ans.pb(b1[i]);
    for(int i = p2.size() - 1; i >= 0; --i)
        ans.pb(p2[i]);
    return ans;
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> XU, vector<int> XV)
{
    vector<int> ans;
    U = XU; V = XV;
    MakeG(n, m);
    DoDel(n);
    if(del[0]) return false;
    MakeG(n, m);
    int v = 0;
    bool abc = true;
    do
    {
        if(kloc[v]) return false;
        kloc[v] = true;
        int il = 0;
        for(int i = 0; i < (int)ed[v].size(); ++i)
            if(!kloc[ed[v][i].st])
                ++il;
        if(il == 0) return false;
        if(il > 1) break;
        abc = true;
        for(int i = 0; i < (int)ed[v].size(); ++i)
            if(!kloc[ed[v][i].st])
            {
                vis[ed[v][i].nd] = true;
                pth.pb(ed[v][i].nd);
                v = ed[v][i].st;
                break;
            }
    }while(abc);

    vector<int> xd = DoC(v, n, m);
    if(xd[0] == -1) return false;
    for(int i = 0; i < (int)pth.size(); ++i)
        ans.pb(pth[i]);
    for(int i = 0; i < (int)xd.size(); ++i)
        ans.pb(xd[i]);
    for(int i = pth.size() - 1; i >= 0; --i)
        ans.pb(pth[i]);

    return ans;
}

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