Submission #418671

#	Time	Username	Problem	Language	Result	Execution time	Memory
418671		Nicholas_Patrick	Senior Postmen (BOI14_postmen)	C++17	100 / 100	468 ms	40004 KiB

postmen

#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 (stderr)

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 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45