Submission #18436

#	Time	Username	Problem	Language	Result	Execution time	Memory
18436		tlwpdus	Senior Postmen (BOI14_postmen)	C++98	0 / 100	149 ms	262148 KiB

postmen

#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);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45