Submission #396138

#	Time	Username	Problem	Language	Result	Execution time	Memory
396138		Nicholas_Patrick	Senior Postmen (BOI14_postmen)	C++17	38 / 100	86 ms	14660 KiB

postmen

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

bitset<1<<23> bloom;
void insert(int x, int y){
	bloom[(x*123456789+y^135798642)*987654321&0x7fffff]=true;
	// bloom[(x*987654321+y^123456789)*135798642&0x7fffff]=true;
	bloom[(x*135798642+y^987654321)*123456789&0x7fffff]=true;
}
bool count(int x, int y){
	return bloom[(x*123456789+y^135798642)*987654321&0x7fffff] and
		// bloom[(x*987654321+y^123456789)*135798642&0x7fffff] and
		bloom[(x*135798642+y^987654321)*123456789&0x7fffff];
}
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	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();
				if(count(x, y)){
					y=-1;
				}else break;
			}
			if(y==-1)break;
			insert(y, 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 'void insert(int, int)':
postmen.cpp:9:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    9 |  bloom[(x*123456789+y^135798642)*987654321&0x7fffff]=true;
      |         ~~~~~~~~~~~^~
postmen.cpp:11:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   11 |  bloom[(x*135798642+y^987654321)*123456789&0x7fffff]=true;
      |         ~~~~~~~~~~~^~
postmen.cpp: In function 'bool count(int, int)':
postmen.cpp:14:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   14 |  return bloom[(x*123456789+y^135798642)*987654321&0x7fffff] and
      |                ~~~~~~~~~~~^~
postmen.cpp:16:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   16 |   bloom[(x*135798642+y^987654321)*123456789&0x7fffff];
      |          ~~~~~~~~~~~^~
postmen.cpp: In function 'int main()':
postmen.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%d%d", &a, &b), a--, b--;
      |   ~~~~~^~~~~~~~~~~~~~~~

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