제출 #1073162

#제출 시각아이디문제언어결과실행 시간메모리
1073162beaconmc수천개의 섬 (IOI22_islands)C++17
0 / 100
114 ms25648 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) const ll maxn = 100005; set<int> edges[maxn]; bool visited[maxn]; bool realvisited[maxn]; bool flag = 0; vector<int> stacks; vector<int> cycle; map<vector<int>, int> idk; map<vector<int>, int> idk2; void dfs(ll a){ if (flag) return; visited[a] = 1; realvisited[a] = 1; stacks.push_back(a); for (auto&i : edges[a]){ if (realvisited[i]){ flag = 1; FORNEG(j,stacks.size()-1, -1){ if (stacks[j]==i) break; else cycle.push_back(stacks[j]); stacks.pop_back(); } cycle.push_back(i); stacks.pop_back(); reverse(cycle.begin(), cycle.end()); return; } else{ if (!visited[i]) visited[i] = 1, dfs(i); } } if (flag) return; stacks.pop_back(); realvisited[a] = 0; } map<vector<int>, vector<int>> crazy; set<vector<int>> visiteds; std::variant<bool, std::vector<int>> find_journey( int N, int M, std::vector<int> U, std::vector<int> V) { flag = 0; FOR(i,0,maxn) visited[i] = 0; FOR(i,0,maxn) edges[i].clear(); FOR(i,0,M){ edges[U[i]].insert(V[i]); if (idk.count({U[i], V[i]})) idk2[{U[i], V[i]}] = i; else idk[{U[i], V[i]}] = i; } dfs(0); if (flag==0) return false; vector<int> journey; for (auto&i : stacks) journey.push_back(i); // for (auto&i : cycle) journey.push_back(i); // for (auto&i : cycle) journey.push_back(i); // journey.push_back(cycle[0]); // journey.push_back(-1); // journey.push_back(cycle[0]); // reverse(cycle.begin(), cycle.end()); // for (auto&i : cycle) journey.push_back(i); // for (auto&i : cycle) journey.push_back(i); // reverse(stacks.begin(), stacks.end()); // for (auto&i : stacks) journey.push_back(i); return true; vector<int> ans; bool idkman = false; FOR(i,1,journey.size()){ if (journey[i-1] == -1) continue; if (journey[i]==-1){ for (auto&i : crazy){ reverse(crazy[i.first].begin(), crazy[i.first].end()); } idkman = true; continue; } if (idkman==0){ if (visiteds.count({journey[i-1], journey[i]})){ ans.push_back(idk2[{journey[i-1], journey[i]}]); crazy[{journey[i],journey[i-1]}].push_back(idk2[{journey[i-1], journey[i]}]); }else{ visiteds.insert({journey[i-1], journey[i]}); ans.push_back(idk[{journey[i-1], journey[i]}]); crazy[{journey[i],journey[i-1]}].push_back(idk[{journey[i-1], journey[i]}]); } }else{ ans.push_back(crazy[{journey[i-1], journey[i]}][crazy[{journey[i-1], journey[i]}].size()-1]); crazy[{journey[i-1], journey[i]}].pop_back(); } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  101 |     FOR(i,1,journey.size()){
      |         ~~~~~~~~~~~~~~~~~~       
islands.cpp:101:5: note: in expansion of macro 'FOR'
  101 |     FOR(i,1,journey.size()){
      |     ^~~
#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...