Submission #1215960

#TimeUsernameProblemLanguageResultExecution timeMemory
1215960user736482Thousands Islands (IOI22_islands)C++20
0 / 100
7 ms10564 KiB
#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();} 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; 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); v[{a.ss,a.ff}].pb(v[{a.ff,a.ss}].back()); v[{a.ff,a.ss}].pop_back(); } while(pom){ pom--; ans.pb(ans[pom]); } //for(ll i : ans)cout<<i<<" "; //cout<<"\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}); } vector<int>ans,ans2; ll ak=0; 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); while(ans2.size()){ ans.pb(ans2.back()); ans2.pop_back(); } return ans; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...