# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25207 | 2017-06-20T19:35:30 Z | minimario | Senior Postmen (BOI14_postmen) | C++14 | 500 ms | 43612 KB |
#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"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12160 KB | Output is correct |
2 | Correct | 12 ms | 12136 KB | Output is correct |
3 | Correct | 11 ms | 12208 KB | Output is correct |
4 | Correct | 13 ms | 12288 KB | Output is correct |
5 | Correct | 15 ms | 12160 KB | Output is correct |
6 | Correct | 13 ms | 12288 KB | Output is correct |
7 | Correct | 18 ms | 12672 KB | Output is correct |
8 | Correct | 12 ms | 12160 KB | Output is correct |
9 | Correct | 59 ms | 15216 KB | Output is correct |
10 | Correct | 13 ms | 12288 KB | Output is correct |
11 | Correct | 13 ms | 12288 KB | Output is correct |
12 | Correct | 68 ms | 15444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 12032 KB | Output is correct |
2 | Correct | 14 ms | 12080 KB | Output is correct |
3 | Correct | 15 ms | 12032 KB | Output is correct |
4 | Correct | 16 ms | 12288 KB | Output is correct |
5 | Correct | 12 ms | 12160 KB | Output is correct |
6 | Correct | 14 ms | 12288 KB | Output is correct |
7 | Correct | 19 ms | 12672 KB | Output is correct |
8 | Correct | 15 ms | 12160 KB | Output is correct |
9 | Correct | 58 ms | 15192 KB | Output is correct |
10 | Correct | 14 ms | 12288 KB | Output is correct |
11 | Correct | 13 ms | 12288 KB | Output is correct |
12 | Correct | 72 ms | 15416 KB | Output is correct |
13 | Correct | 101 ms | 18420 KB | Output is correct |
14 | Correct | 113 ms | 17944 KB | Output is correct |
15 | Correct | 92 ms | 18796 KB | Output is correct |
16 | Correct | 105 ms | 18420 KB | Output is correct |
17 | Correct | 140 ms | 18424 KB | Output is correct |
18 | Correct | 106 ms | 18044 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12032 KB | Output is correct |
2 | Correct | 11 ms | 12160 KB | Output is correct |
3 | Correct | 14 ms | 12032 KB | Output is correct |
4 | Correct | 17 ms | 12288 KB | Output is correct |
5 | Correct | 16 ms | 12160 KB | Output is correct |
6 | Correct | 13 ms | 12288 KB | Output is correct |
7 | Correct | 23 ms | 12672 KB | Output is correct |
8 | Correct | 13 ms | 12160 KB | Output is correct |
9 | Correct | 75 ms | 15216 KB | Output is correct |
10 | Correct | 15 ms | 12288 KB | Output is correct |
11 | Correct | 15 ms | 12212 KB | Output is correct |
12 | Correct | 62 ms | 15384 KB | Output is correct |
13 | Correct | 103 ms | 18468 KB | Output is correct |
14 | Correct | 110 ms | 17944 KB | Output is correct |
15 | Correct | 98 ms | 18928 KB | Output is correct |
16 | Correct | 106 ms | 18476 KB | Output is correct |
17 | Correct | 111 ms | 18352 KB | Output is correct |
18 | Correct | 113 ms | 17992 KB | Output is correct |
19 | Execution timed out | 653 ms | 43612 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |