# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
18436 | 2016-02-01T17:18:53 Z | tlwpdus | Senior Postmen (BOI14_postmen) | C++ | 149 ms | 262148 KB |
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> #include<string.h> using namespace std; int n, m; int beg[1000100], des[1000100], nxt[1000100], pre[1000100]; vector<int> euler; queue<int> chk[500100]; void erase_edge(int ptr, int v) { if (beg[v]==ptr) beg[v]=nxt[ptr]; if (pre[ptr]!=-1) nxt[pre[ptr]] = nxt[ptr]; if (nxt[ptr]!=-1) pre[nxt[ptr]] = pre[ptr]; des[ptr] = -1; } int find(int u) { if (u==-1||des[u]!=-1) return u; return nxt[u] = find(nxt[u]); } void dfs(int here) { int i; for (i=beg[here];i!=-1;i=find(i)) { int there = des[i]; erase_edge(i,here); erase_edge(i^1,there); dfs(there); } chk[here].push(euler.size()); euler.push_back(here); } int key = 0; vector<int> res[500100]; int ans(int s, int e) { int i, hkey = key++; for (i=s;i<e;i++) { if (i!=s) chk[euler[i]].pop(); if (i!=s&&!chk[euler[i]].empty()&&chk[euler[i]].front()<e) i = ans(i,chk[euler[i]].front()); res[hkey].push_back(euler[i]); } return i; } void process() { dfs(0); chk[euler[0]].pop(); ans(0,euler.size()-1); for (int i=0;i<key;i++) { for (int j=0;j<res[i].size();j++) printf("%d ",res[i][j]+1); printf("\n"); } } int ptr = 0; void real_add_edge(int u, int v) { nxt[ptr] = beg[u]; pre[beg[u]] = ptr; des[ptr] = v; pre[ptr] = -1; beg[u] = ptr++; } void add_edge(int u, int v) {real_add_edge(u,v);real_add_edge(v,u);} void input() { int i; scanf("%d %d",&n,&m); memset(beg,-1,sizeof(beg)); for (i=0;i<m;i++) { int a, b; scanf("%d %d",&a,&b); add_edge(--a,--b); } } int main() { input(); process(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 145 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 149 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 137 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |