이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |