oj.uz

Submission #42315

# Submission time Handle Problem Language Result Execution time Memory
42315 2018-02-26T01:17:30 Z IvanC Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 108048 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAXN = 5*1e5 + 10;
int N,M,posicao[MAXN],marcado[MAXN];
set<int> cjt[MAXN];
vi pilha,temporario;
vector<vi> resposta;
void dfs(int v){
	marcado[v] = 1;
	posicao[v] = pilha.size();
	pilha.push_back(v);
	while(!cjt[v].empty() && posicao[v] != -1){
		int u = *(cjt[v].begin());
		cjt[v].erase(u);
		cjt[u].erase(v);
		if(marcado[u]){
			for(int i = posicao[v];i>posicao[u];i--){
				int k = pilha[i];
				posicao[k] = -1;
				marcado[k] = 0;
				temporario.push_back(k);
				pilha.pop_back(); 
			}
			temporario.push_back(u);
			resposta.push_back(temporario);
			temporario.clear();
			return;
		}
		else{
			dfs(u);
		}
	}
	if(posicao[v] == -1) return;
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++) posicao[i] = -1;
	for(int i = 1;i<=M;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		cjt[u].insert(v);
		cjt[v].insert(u);
	}
	for(int i = 1;i<=N;i++){
		if(!cjt[i].empty()) dfs(i);
	}
	for(int i = 0;i<resposta.size();i++){
		for(int j : resposta[i]) printf("%d ",j);
		printf("\n");
	}
	return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<resposta.size();i++){
                ~^~~~~~~~~~~~~~~~
postmen.cpp:37: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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct
3 Correct 22 ms 23784 KB Output is correct
4 Correct 21 ms 24192 KB Output is correct
5 Correct 19 ms 24020 KB Output is correct
6 Correct 25 ms 24340 KB Output is correct
7 Correct 36 ms 25496 KB Output is correct
8 Correct 23 ms 24192 KB Output is correct
9 Correct 198 ms 34388 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 27 ms 24192 KB Output is correct
12 Correct 190 ms 34420 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23804 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 21 ms 24192 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 22 ms 24320 KB Output is correct
7 Correct 33 ms 25472 KB Output is correct
8 Correct 21 ms 24192 KB Output is correct
9 Correct 201 ms 34268 KB Output is correct
10 Correct 19 ms 24192 KB Output is correct
11 Correct 26 ms 24168 KB Output is correct
12 Correct 176 ms 34396 KB Output is correct
13 Correct 126 ms 40816 KB Output is correct
14 Correct 155 ms 38488 KB Output is correct
15 Correct 153 ms 35440 KB Output is correct
16 Correct 138 ms 40740 KB Output is correct
17 Correct 181 ms 35440 KB Output is correct
18 Correct 155 ms 36972 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 24192 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 21 ms 24320 KB Output is correct
7 Correct 35 ms 25464 KB Output is correct
8 Correct 20 ms 24192 KB Output is correct
9 Correct 199 ms 34336 KB Output is correct
10 Correct 19 ms 24192 KB Output is correct
11 Correct 20 ms 24192 KB Output is correct
12 Correct 206 ms 34412 KB Output is correct
13 Correct 137 ms 40792 KB Output is correct
14 Correct 163 ms 38448 KB Output is correct
15 Correct 169 ms 35352 KB Output is correct
16 Correct 132 ms 40816 KB Output is correct
17 Correct 168 ms 35416 KB Output is correct
18 Correct 157 ms 36952 KB Output is correct
19 Execution timed out 656 ms 108048 KB Time limit exceeded
20 Halted 0 ms 0 KB -