제출 #1062096

#제출 시각아이디문제언어결과실행 시간메모리
1062096jamjanek수천개의 섬 (IOI22_islands)C++17
9.10 / 100
171 ms65056 KiB
#include "islands.h" #include<bits/stdc++.h> using namespace std; int stopien_wyjscia[100010]; set<pair<int, int>>graf[100010], graf1[100010]; bool usuniete[100010]; vector<int>answer; bool czy[100010]; bool odw1[100010]; vector<int>stos; bool flaga_znaleziono = 0; void dfs(int start){ czy[start] = 1; odw1[start] = 1; for(auto j: graf[start]){ if(czy[j.first]){ stos.push_back(j.second); flaga_znaleziono = 1; return; } if(!odw1[j.first]){ stos.push_back(j.second); dfs(j.first); if(flaga_znaleziono)return; stos.pop_back(); } } czy[start] = 0; } variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U, std::vector<int> V) { int i; for(i=0;i<m;i++){ graf[U[i]].insert({V[i], i}); graf1[V[i]].insert({U[i], i}); stopien_wyjscia[U[i]]++; //graf[V[i]].push_back({U[i], i+1}); } int start = 0; queue<int>kolejka; for(i=0;i<n;i++) if(stopien_wyjscia[i]==0) kolejka.push(i); vector<int>poczatek; while(true){ // printf("%d\n", start); // for(i=0;i<n;i++)printf("%d ", stopien_wyjscia[i]);printf("\n"); if(stopien_wyjscia[start]==0)return false; if(stopien_wyjscia[start]==1){ for(auto j: graf1[start]) if(--stopien_wyjscia[j.first]==0) kolejka.push(j.first); usuniete[start] = 1; for(auto j: graf[start]) if(!usuniete[j.first]){ start = j.first; answer.push_back(j.second); break; } continue; } if(!kolejka.size())break; auto x = kolejka.front(); kolejka.pop(); if(usuniete[x])continue; usuniete[x] = 1; for(auto j: graf1[x]) if(--stopien_wyjscia[j.first]==0) kolejka.push(j.first); } if(stopien_wyjscia[start]<=1)return false; poczatek = answer; for(i=0;i<n;i++){ vector<pair<int,int>>do_usu; for(auto j: graf[i]) if(usuniete[j.first])do_usu.push_back(j); for(auto j: do_usu) graf[i].erase(j); } czy[start] = 1; odw1[start] = 1; stos.push_back((*graf[start].begin()).second); dfs((*graf[start].begin()).first); vector<int>pierwsza = stos; stos.clear(); for(i=0;i<n;i++)odw1[i] = 0; czy[start] = 1; odw1[start] = 1; stos.push_back((*graf[start].rbegin()).second); if(!czy[(*graf[start].rbegin()).second]) dfs((*graf[start].rbegin()).second); vector<int>druga = stos; // for(auto j: pierwsza)printf("%d ", j);printf("\n"); // for(auto j: druga)printf("%d ", j);printf("\n"); for(i=0;i<n;i++)graf[i].clear(); for(auto j: pierwsza) graf[U[j]].insert({V[j], j}); for(auto j: druga) graf[U[j]].insert({V[j], j}); int x = start; int policz = 0, pop = -1; while(true){ // printf("%d, ", x); if(x==start)policz++; if(policz==13)break; auto it = *graf[x].begin(); if(it.second==pop) it = *graf[x].rbegin(); answer.push_back(it.second); graf[x].erase(it); graf[it.first].insert({x, it.second}); x = it.first; pop = it.second; } while(poczatek.size()){ answer.push_back(poczatek.back()); poczatek.pop_back(); } return answer; }
#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...