oj.uz

Submission #418671

# Submission time Handle Problem Language Result Execution time Memory
418671 2021-06-05T17:19:19 Z Nicholas_Patrick Senior Postmen (BOI14_postmen) C++17
100 / 100
 468 ms 40004 KB 
#include <cstdio>
#include <queue>
#include <bitset>
using namespace std;

const int maxn=5e5;
struct edge{
	int t, rev;
	bool used;
	edge(int t, int rev):t(t), rev(rev), used(false){}
};
vector<edge> adjlis[maxn];
bitset<maxn> visited;
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int sz1, sz2;
	while(m--){
		int u, v;
		scanf("%d%d", &u, &v), u--, v--;
		sz1=adjlis[u].size();
		sz2=adjlis[v].size();
		adjlis[u].emplace_back(v, sz2);
		adjlis[v].emplace_back(u, sz1);
	}
	vector<int> circuit, simp;
	circuit.reserve(n);
	simp.reserve(n);
	for(int i=0; i<n; i++){
		while(not adjlis[i].empty()){
			while(not adjlis[i].empty() and adjlis[i].back().used)
				adjlis[i].pop_back();
			if(adjlis[i].empty())
				break;
			circuit.push_back(i);
			do{
				int bk=circuit.back();
				while(not adjlis[bk].empty() and adjlis[bk].back().used)
					adjlis[bk].pop_back();
				circuit.push_back(adjlis[bk].back().t);
				adjlis[adjlis[bk].back().t][adjlis[bk].back().rev].used=true;
				adjlis[bk].pop_back();
			}while(circuit.back()!=i);
			circuit.pop_back();
			for(int i : circuit){
				if(visited[i]){
					while(simp.back()!=i){
						printf("%d ", simp.back()+1);
						visited[simp.back()]=false;
						simp.pop_back();
					}
					printf("%d\n", simp.back()+1);
					visited[simp.back()]=false;
					simp.pop_back();
				}
				simp.push_back(i);
				visited[i]=true;
			}
			while(simp.size()>1){
				printf("%d ", simp.back()+1);
				visited[simp.back()]=false;
				simp.pop_back();
			}
			printf("%d\n", simp.back()+1);
			visited[simp.back()]=false;
			simp.pop_back();
			circuit.clear();
		}
	}
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d%d", &u, &v), u--, v--;
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 8 ms 12040 KB Output is correct
5 Correct 7 ms 12032 KB Output is correct
6 Correct 9 ms 12168 KB Output is correct
7 Correct 13 ms 12820 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 42 ms 16080 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Correct 9 ms 12128 KB Output is correct
12 Correct 47 ms 16708 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 9 ms 12036 KB Output is correct
5 Correct 8 ms 12052 KB Output is correct
6 Correct 9 ms 12200 KB Output is correct
7 Correct 14 ms 12808 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 43 ms 16004 KB Output is correct
10 Correct 9 ms 12152 KB Output is correct
11 Correct 9 ms 12108 KB Output is correct
12 Correct 47 ms 16724 KB Output is correct
13 Correct 67 ms 17596 KB Output is correct
14 Correct 86 ms 16908 KB Output is correct
15 Correct 57 ms 16496 KB Output is correct
16 Correct 70 ms 17652 KB Output is correct
17 Correct 65 ms 16856 KB Output is correct
18 Correct 63 ms 17304 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 12032 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 10 ms 12108 KB Output is correct
5 Correct 8 ms 11980 KB Output is correct
6 Correct 11 ms 12236 KB Output is correct
7 Correct 13 ms 12780 KB Output is correct
8 Correct 8 ms 12036 KB Output is correct
9 Correct 44 ms 15992 KB Output is correct
10 Correct 8 ms 12108 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 47 ms 16744 KB Output is correct
13 Correct 67 ms 17596 KB Output is correct
14 Correct 63 ms 17004 KB Output is correct
15 Correct 63 ms 16512 KB Output is correct
16 Correct 64 ms 17572 KB Output is correct
17 Correct 65 ms 16900 KB Output is correct
18 Correct 62 ms 17308 KB Output is correct
19 Correct 441 ms 36464 KB Output is correct
20 Correct 442 ms 33544 KB Output is correct
21 Correct 393 ms 30828 KB Output is correct
22 Correct 444 ms 38300 KB Output is correct
23 Correct 191 ms 30916 KB Output is correct
24 Correct 468 ms 37648 KB Output is correct
25 Correct 422 ms 40004 KB Output is correct