Submission #1215971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215971		user736482	Thousands Islands (IOI22_islands)	C++20	55.15 / 100	835 ms	63148 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;
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;
        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]);}
        ans.pb(v[{x,nxt}].back());
        pop=ans.back();
        vp.pb({x,nxt});
        odw[x]=1;
        x=nxt;
    }
   // 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);
    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);

            for(ll i : v1)ans.pb(i);

            for(ll i : v2)ans.pb(i);

            v1=cycle(ak,0);
            v2=cycle(ak,1);
            for(ll i : v1)ans.pb(i);
            for(ll i : v2)ans.pb(i);
            v1=cycle(ak,0);
            v2=cycle(ak,1);
            for(ll i : v1)ans.pb(i);
            for(ll i : v2)ans.pb(i);
            v1=cycle(ak,0);
            v2=cycle(ak,1);
            for(ll i : v1)ans.pb(i);
            for(ll i : v2)ans.pb(i);
            v1=cycle(ak,0);
            v2=cycle(ak,1);
            for(ll i : v1)ans.pb(i);
            for(ll i : v2)ans.pb(i);
            v1=cycle(ak,0);
            v2=cycle(ak,1);
            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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 8.4 / 24
• Subtask 5: 15.75 / 45