Submission #396096

#	Time	Username	Problem	Language	Result	Execution time	Memory
396096		Nicholas_Patrick	Senior Postmen (BOI14_postmen)	C++17	55 / 100	619 ms	42832 KiB

postmen

#include <cstdio>
#include <queue>
#include <unordered_set>
using namespace std;

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	unordered_set<long long> deleted;
	vector<vector<int>> adjLis(n);
	for(int i=m; i--;){
		int a, b;
		scanf("%d%d", &a, &b), a--, b--;
		adjLis[a].push_back(b);
		adjLis[b].push_back(a);
	}
	vector<bool> visited(n, false);
	for(int i=n; i--;){
		int x=i;
		vector<int> ans;
		while(not adjLis[i].empty()){
			ans.push_back(x);
			visited[x]=true;
			int y=-1;
			for(;not adjLis[i].empty();){
				y=adjLis[x].back();
				adjLis[x].pop_back();
				auto it=deleted.find((long long)x<<30|y);
				if(it!=deleted.end()){
					deleted.erase(it);
					y=-1;
				}else break;
			}
			if(y==-1)break;
			deleted.insert((long long)y<<30|x);
			if(visited[y]){
				while(ans.back()!=y){
					printf("%d ", ans.back()+1);
					visited[ans.back()]=false;
					ans.pop_back();
				}
				printf("%d\n", ans.back()+1);
				visited[ans.back()]=false;
				ans.pop_back();
				x=y;
			}else{
				x=y;
			}
		}
	}
}

Compilation message (stderr)

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45