Submission #18436

#TimeUsernameProblemLanguageResultExecution timeMemory
18436tlwpdusSenior Postmen (BOI14_postmen)C++98
0 / 100
149 ms262148 KiB
#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 (stderr)

postmen.cpp: In function 'void process()':
postmen.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<res[i].size();j++) printf("%d ",res[i][j]+1);
                ~^~~~~~~~~~~~~~
postmen.cpp: In function 'void input()':
postmen.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
postmen.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...