oj.uz

Submission #42316

# Submission time Handle Problem Language Result Execution time Memory
42316 2018-02-26T01:20:33 Z IvanC Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 108224 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].rbegin());
		cjt[v].erase(cjt[v].find(u));
		cjt[u].erase(cjt[u].find(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 24 ms 23808 KB Output is correct
2 Correct 19 ms 23784 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 24 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 32 ms 25472 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 200 ms 34328 KB Output is correct
10 Correct 25 ms 24192 KB Output is correct
11 Correct 21 ms 24192 KB Output is correct
12 Correct 193 ms 34400 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 23 ms 23776 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 22 ms 24192 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Correct 22 ms 24368 KB Output is correct
7 Correct 37 ms 25472 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 192 ms 34268 KB Output is correct
10 Correct 24 ms 24192 KB Output is correct
11 Correct 20 ms 24192 KB Output is correct
12 Correct 169 ms 34392 KB Output is correct
13 Correct 124 ms 40816 KB Output is correct
14 Correct 141 ms 38512 KB Output is correct
15 Correct 162 ms 35376 KB Output is correct
16 Correct 136 ms 40752 KB Output is correct
17 Correct 165 ms 35416 KB Output is correct
18 Correct 154 ms 36896 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 23 ms 24296 KB Output is correct
5 Correct 20 ms 23912 KB Output is correct
6 Correct 21 ms 24320 KB Output is correct
7 Correct 35 ms 25440 KB Output is correct
8 Correct 20 ms 24192 KB Output is correct
9 Correct 205 ms 34316 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 25 ms 24192 KB Output is correct
12 Correct 186 ms 34420 KB Output is correct
13 Correct 154 ms 40816 KB Output is correct
14 Correct 154 ms 38416 KB Output is correct
15 Correct 163 ms 35408 KB Output is correct
16 Correct 126 ms 40816 KB Output is correct
17 Correct 167 ms 35460 KB Output is correct
18 Correct 152 ms 36936 KB Output is correct
19 Execution timed out 666 ms 108224 KB Time limit exceeded
20 Halted 0 ms 0 KB -