oj.uz

Submission #115962

# Submission time Handle Problem Language Result Execution time Memory
115962 2019-06-10T04:56:57 Z Mahdi_Jfri Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 58368 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;

vector<int> adj[maxn] , path;

int from[maxn] , to[maxn];

bool visited[maxn];

void dfs(int v)
{
	while(!adj[v].empty())
	{
		int e = adj[v].back() , u = from[e] ^ to[e] ^ v;
		adj[v].pop_back();

		if(visited[e])
			continue;

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

int main()
{
	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--;

		adj[a].pb(i);
		adj[b].pb(i);

		from[i] = a , to[i] = 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:34: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:39: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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12544 KB Output is correct
2 Correct 11 ms 12576 KB Output is correct
3 Correct 12 ms 12544 KB Output is correct
4 Correct 14 ms 12800 KB Output is correct
5 Correct 13 ms 12672 KB Output is correct
6 Correct 20 ms 12800 KB Output is correct
7 Correct 20 ms 13544 KB Output is correct
8 Correct 16 ms 12700 KB Output is correct
9 Correct 63 ms 18392 KB Output is correct
10 Correct 14 ms 12800 KB Output is correct
11 Correct 17 ms 12800 KB Output is correct
12 Correct 85 ms 18548 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12544 KB Output is correct
2 Correct 12 ms 12544 KB Output is correct
3 Correct 14 ms 12544 KB Output is correct
4 Correct 17 ms 12800 KB Output is correct
5 Correct 14 ms 12672 KB Output is correct
6 Correct 14 ms 12800 KB Output is correct
7 Correct 20 ms 13568 KB Output is correct
8 Correct 16 ms 12800 KB Output is correct
9 Correct 64 ms 18904 KB Output is correct
10 Correct 16 ms 12784 KB Output is correct
11 Correct 16 ms 12776 KB Output is correct
12 Correct 74 ms 19420 KB Output is correct
13 Correct 126 ms 22356 KB Output is correct
14 Correct 129 ms 19832 KB Output is correct
15 Correct 111 ms 20720 KB Output is correct
16 Correct 105 ms 22264 KB Output is correct
17 Correct 107 ms 18136 KB Output is correct
18 Correct 101 ms 20444 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12544 KB Output is correct
2 Correct 14 ms 12544 KB Output is correct
3 Correct 15 ms 12544 KB Output is correct
4 Correct 13 ms 12800 KB Output is correct
5 Correct 13 ms 12672 KB Output is correct
6 Correct 13 ms 12928 KB Output is correct
7 Correct 19 ms 13672 KB Output is correct
8 Correct 16 ms 12800 KB Output is correct
9 Correct 56 ms 19056 KB Output is correct
10 Correct 15 ms 12800 KB Output is correct
11 Correct 14 ms 12724 KB Output is correct
12 Correct 64 ms 19444 KB Output is correct
13 Correct 100 ms 22256 KB Output is correct
14 Correct 103 ms 19888 KB Output is correct
15 Correct 88 ms 20696 KB Output is correct
16 Correct 104 ms 22220 KB Output is correct
17 Correct 106 ms 18136 KB Output is correct
18 Correct 98 ms 20440 KB Output is correct
19 Execution timed out 627 ms 58368 KB Time limit exceeded
20 Halted 0 ms 0 KB -