oj.uz

Submission #18438

# Submission time Handle Problem Language Result Execution time Memory
18438 2016-02-01T17:27:35 Z tlwpdus Senior Postmen (BOI14_postmen) C++
0 / 100
 95 ms 68600 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>

#define MAXN 100100
#define MAXM 100100

using namespace std;

int n, m;
int beg[2*MAXM], des[2*MAXM], nxt[2*MAXM], pre[2*MAXM];
vector<int> euler;
queue<int> chk[MAXN];
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);
}
queue<pair<int,int> > q;
void ans() {
	int i;
	q.push(pair<int,int>(0,euler.size()-1));
	while(!q.empty()) {
		int s = q.front().first, e = q.front().second;
		q.pop();
		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) {
				q.push(pair<int,int>(i,chk[euler[i]].front()));
				i=chk[euler[i]].front();
			}
			printf("%d ",euler[i]+1);
		}
		printf("\n");
	}
}
void process() {
	dfs(0);
	chk[euler[0]].pop();
	ans();
}
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

postmen.cpp: In function 'void input()':
postmen.cpp:71: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:75: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.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 68480 KB Output is correct
2 Correct 95 ms 68472 KB Output is correct
3 Incorrect 53 ms 68600 KB Some edges were not used
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 68472 KB Output is correct
2 Correct 65 ms 68600 KB Output is correct
3 Incorrect 48 ms 68448 KB Some edges were not used
4 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 68448 KB Output is correct
2 Correct 49 ms 68480 KB Output is correct
3 Incorrect 51 ms 68472 KB Some edges were not used
4 Halted 0 ms 0 KB -