Submission #1240917

#TimeUsernameProblemLanguageResultExecution timeMemory
1240917nikulidThousands Islands (IOI22_islands)C++20
6.75 / 100
19 ms5188 KiB
#include "islands.h" #include <map> #include <variant> #include <vector> #include <algorithm> using namespace std; #define pb push_back #define mp make_pair variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { vector<int> answer; if(N==2){ // subtask 1 vector<int> A, B; for(int i=0; i<M; i++){ if(U[i]==0 && V[i]==1){ A.pb(i); } else{ B.pb(i); } } if(A.size()>1 && B.size()>0){ answer = {A[0], B[0], A[1], A[0], B[0], A[1]}; return answer; } else{ return false; } } // subtask 3 (21 marks) vector<vector<pair<int, int>>> ns(N); // ns[node] = { {canoe1, nextIsland}, {canoe2, nextIsland}, {canoe3, nextIsland}, ...} int u,v; for(int i=0; i<M; i++){ u=U[i]; v=V[i]; ns[u].pb( mp(i,v) ); } // simple case (same as subtask 2) if(ns[0].size() == 0){ return false; } else if(ns[0].size() > 1){ int a=ns[0][0].first; int b; if(a%2==0) b=a+1; else b=a-1; //int b = ((a%2==0) ? a+1 : a-1); int c=ns[0][1].first; int d; if(c%2==0) d=c+1; else d=c-1; //int d = ((c%2==0) ? c+1 : c-1); answer = {a,b,c,d,b,a,d,c}; return answer; } // complex case int prevc = ns[0][0].first; int prev = 0; int cur = ns[0][0].second; vector<int> pretrip = {ns[0][0].first}; vector<int> trip; while(true){ if(ns[cur].size() == 1){ // there is only one canoe that started from this island return false; } else if(ns[cur].size() == 2){ // this island is merely part of the pretrip if(ns[cur][0].first == prevc){ prev = cur; cur = ns[cur][1].second; prevc = ns[cur][1].first; } else{ prev = cur; cur = ns[cur][0].second; prevc = ns[cur][0].first; } pretrip.pb(prevc); } else{ // trip located! return true; } } }
#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...