oj.uz

답안 #115966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115966 2019-06-10T05:05:34 Z Mahdi_Jfri 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 342 ms 43480 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;

vector<int> path;

int from[maxn] , to[maxn] , last[maxn] , head[maxn] , id;

bool visited[maxn];

void add_edge(int v , int u)
{
	from[id] = v , to[id] = u , last[id] = head[v] , head[v] = id , id++;
	from[id] = u , to[id] = v , last[id] = head[u] , head[u] = id , id++;
}

void dfs(int v)
{
	while(head[v] != -1)
	{
		int e = head[v] , u = to[e];
		head[v] = last[e];

		if(visited[e / 2])
			continue;

		visited[e / 2] = 1;
		dfs(u);
	}
	path.pb(v);
}

int main()
{
	memset(head , -1 , sizeof head);
	int n , m;
	scanf("%d%d", &n, &m);

	for(int i = 0; i < m; i++)
	{
		int a , b;
		scanf("%d%d", &a, &b);
		a-- , b--;

		add_edge(a , b);
	}

	dfs(0);

	vector<int> tmp;
	memset(visited , 0 , sizeof visited);
	for(auto v : path)
	{
		if(visited[v])
		{
			while(tmp.back() != v)
			{
				printf("%d ", tmp.back() + 1);
				visited[tmp.back()] = 0;
				tmp.pop_back();
			}
			tmp.pop_back();
			printf("%d\n", v + 1);
		}

		tmp.pb(v);
		visited[v] = 1;
	}
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:41: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:46: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
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 8 ms 5552 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 11 ms 5504 KB Output is correct
7 Correct 13 ms 6272 KB Output is correct
8 Correct 9 ms 5376 KB Output is correct
9 Correct 48 ms 12316 KB Output is correct
10 Correct 9 ms 5376 KB Output is correct
11 Correct 12 ms 5376 KB Output is correct
12 Correct 51 ms 12504 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 9 ms 5376 KB Output is correct
6 Correct 9 ms 5632 KB Output is correct
7 Correct 13 ms 6368 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 48 ms 11752 KB Output is correct
10 Correct 8 ms 5376 KB Output is correct
11 Correct 10 ms 5376 KB Output is correct
12 Correct 60 ms 11760 KB Output is correct
13 Correct 68 ms 12344 KB Output is correct
14 Correct 54 ms 10608 KB Output is correct
15 Correct 52 ms 11632 KB Output is correct
16 Correct 57 ms 12272 KB Output is correct
17 Correct 59 ms 8944 KB Output is correct
18 Correct 54 ms 11120 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 11 ms 5608 KB Output is correct
7 Correct 14 ms 6272 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 48 ms 11632 KB Output is correct
10 Correct 8 ms 5376 KB Output is correct
11 Correct 9 ms 5400 KB Output is correct
12 Correct 65 ms 11632 KB Output is correct
13 Correct 59 ms 12248 KB Output is correct
14 Correct 54 ms 10612 KB Output is correct
15 Correct 50 ms 11632 KB Output is correct
16 Correct 58 ms 12272 KB Output is correct
17 Correct 54 ms 8944 KB Output is correct
18 Correct 57 ms 11120 KB Output is correct
19 Correct 339 ms 40056 KB Output is correct
20 Correct 320 ms 35532 KB Output is correct
21 Correct 315 ms 40908 KB Output is correct
22 Correct 342 ms 43480 KB Output is correct
23 Correct 217 ms 40180 KB Output is correct
24 Correct 341 ms 27040 KB Output is correct
25 Correct 323 ms 38280 KB Output is correct