Submission #1216018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216018		user736482	Thousands Islands (IOI22_islands)	C++20	10.85 / 100	344 ms	53732 KiB

islands

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

multiset<ll>g[100007],g2[100007];
map<pair<ll,ll>,vector<ll>>v;
map<pair<ll,ll>,pair<ll,ll>>nx;
bool us[100007];
bool odw[100007];
ll pop=-1;
queue<pair<ll,ll>>q;
void upd(){
    while(q.size()){
        auto pom=q.front();
        //cout<<pom.ff<<" "<<pom.ss<<"\n";
        v[pom].pop_back();
        q.pop();
        g[pom.ff].erase(g[pom.ff].lower_bound(pom.ss));
        g2[pom.ss].erase(g2[pom.ss].lower_bound(pom.ff));
        if(g[pom.ff].empty())for(ll j : g2[pom.ff])q.push({j,pom.ff});
    }
}

vector<ll>cycle(ll x,bool bl){
    for(ll i=0;i<100007;i++)odw[i]=0;
    vector<ll>ans,ak;
    vector<pair<ll,ll>>vp;
    while(!odw[x]){
        //cout<<x<<"  ";
        ak.pb(x);
        ll nxt;
        bool bll=0;
        nxt=*g[x].begin();
        if(pop==v[{x,nxt}].back()){
            //cout<<"xd";
        nxt=*--g[x].end();
        swap(v[{x,nxt}].back(),v[{x,nxt}][0]);
        bll=1;
        }
        ans.pb(v[{x,nxt}].back());
        pop=ans.back();
        vp.pb({x,nxt});
        odw[x]=1;
        
        if(bl && us[v[{x,nxt}].back()]){
            ll l=ans.size()-2;
            pair<ll,ll> akk={x,nxt};
            //akk={akk.ss,akk.ff};
            pair<ll,ll> ak2=nx[akk];
            //akk={akk.ss,akk.ff};
            //ak2={ak2.ss,ak2.ff};
            while(ak2!=akk){
                vp.pb(ak2);//cout<<ak2.ff<<" "<<ak2.ss<<flush;
                ans.pb(v[ak2].back());
                //cout<<ak2.ff<<" "<<ak2.ss<<"  "<<flush;
               // ak2={ak2.ss,ak2.ff};
                ak2=nx[ak2];
                //ak2={ak2.ss,ak2.ff};
                ak.pb(ak2.ff);
                pop=ans.back();
            }
            while(l>=0){ans.pb(ans[l--]);pop=ans.back();}
            ans.pb(-1);
            return ans;
        }
        else{//if(bll && bl)
        //swap(v[{x,nxt}].back(),v[{x,nxt}][0]);
        x=nxt;
        }
    }
    return {0};
    //cout<<"xd"<<flush;
    ak.pb(-1);
    ll pom=ak.size()-1;
    vector<pair<pair<ll,ll>,ll>>vm;
    while(x!=ak.back()){
        ak.pop_back();
        pom--;
        auto a=vp[pom];
        //cout<<a.ff<<" "<<a.ss<<"\n";
        g[a.ff].erase(g[a.ff].find(a.ss));
        g[a.ss].insert(a.ff);
        vm.pb({{a.ss,a.ff},v[{a.ff,a.ss}].back()});
        v[{a.ff,a.ss}].pop_back();
    }
    for(auto i : vm)v[i.ff].pb(i.ss);//cout<<pom<<" ";
    if(!bl)
    for(ll i=0;i<vm.size();i++){us[v[vm[i].ff].back()]=1;nx[vm[i].ff]=vm[(i+vm.size()+1)%(vm.size())].ff;//cout<<vm[i].ff.ff<<" "<<vm[i].ff.ss<<"\n";
    }
    while(pom){
        pom--;
        ans.pb(ans[pom]);
    }
    //for(ll i : ans)cout<<i<<" ";
    //cout<<"\n\n"<<flush;
    pop=ans.back();
    return ans;
}

variant<bool,vector<int>>find_journey(int n,int m,vector<int>u,vector<int>w){
    for(ll i=0;i<m;i++){
        g[u[i]].insert(w[i]);
        g2[w[i]].insert(u[i]);
        v[{u[i],w[i]}].pb(i);
    }
    
    for(ll i=0;i<n;i++){
    if(g[i].empty())for(ll j : g2[i])q.push({j,i});
    }
    upd();
    vector<int>ans,ans2;
    ll ak=0;
    //cout<<"xd";
    while(1){
        if(g[ak].empty())return false;
        else if(g[ak].size()==1){
            q.push({ak,*g[ak].begin()});
            ans.pb(v[{ak,*g[ak].begin()}].back());
            ans2.pb(v[{ak,*g[ak].begin()}].back());
            ak=*g[ak].begin();
            upd();
        }
        else{
            
            auto v1=cycle(ak,0);
            auto v2=cycle(ak,1);
            bool bl=0;
            if(v2.back()==-1){
                bl=1;
                v2.pop_back();
            }
            for(ll i : v1)ans.pb(i);

            for(ll i : v2)ans.pb(i);
            if(bl){
                while(ans2.size()){
                ans.pb(ans2.back());
                ans2.pop_back();
            }
            return ans;
            }
            return ans;
            reverse(v1.begin(),v1.end());
            reverse(v2.begin(),v2.end());
            for(ll i : v1)ans.pb(i);
            for(ll i : v2)ans.pb(i);
            while(ans2.size()){
                ans.pb(ans2.back());
                ans2.pop_back();
            }
            return ans;
        }
    }
}

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