# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
25207 | minimario | 어르신 집배원 (BOI14_postmen) | C++14 | 653 ms | 43612 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) FOR(i, 0, a)
const int MAX = 500005;
const int MAXN = 1000005;
const int MOD = 1000000007;
const int MAGIC = 3;
template <typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
if ( !v.empty() ) {
out << '[';
std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
out << "\b\b]";
}
return out;
}
int e1[MAXN], e2[MAXN], banned[MAXN]; // edges, and dif the edge is banned
vi g[MAX];
void remove_edges(int u) {
while (!g[u].empty() && banned[g[u].back()]) {
g[u].pop_back();
}
}
int v[MAX];
vector<vi> answer;
void chain(int u) {
vi ord;
int st = u;
while (!g[st].empty()) {
ord.pb(st);
int e = g[st].back(); banned[e] = true;
int from = st, to = e1[e] + e2[e] - from;
remove_edges(from); remove_edges(to);
st = to;
}
ord.pb(st);
vi cycle, cur;
for (int i : ord) {
cur.pb(i);
v[i]++;
if (v[i] >= 2) {
do {
v[cur.back()]--;
cycle.pb(cur.back());
cur.pop_back();
} while (cur.back() != i);
cycle.pb(cycle[0]);
answer.pb(cycle);
cycle.clear();
}
}
for (int i : cur) { v[i]--; }
}
int main() {
int num = 0; // number of edge
int n, m; scanf("%d %d", &n, &m);
F0R(i, m) {
int a, b; scanf("%d %d", &a, &b);
e1[i] = a; e2[i] = b;
g[a].pb(i); g[b].pb(i); num++;
}
FOR(i, 1, n+1) { chain(i); }
for (vector<int> i : answer) { num -= i.size(); num++; }
if (num == 0) {
for (vector<int> i : answer) {
FOR(moo, 1, i.size()) {
printf("%d", i[moo]);
if (moo == (int) i.size() - 1) { printf("\n"); }
else { printf(" "); }
}
}
}
else { printf("NIE\n"); }
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |