Submission #396153

#	Time	Username	Problem	Language	Result	Execution time	Memory
396153		Nicholas_Patrick	Senior Postmen (BOI14_postmen)	C++17	100 / 100	449 ms	49588 KiB

postmen

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

bitset<1<<27> bloom;
inline void insert(int x, int y){
	bloom[(x*123456789+y^135798642)*987654321&0x7ffffff]=true;
	bloom[(x*987654321+y^123456789)*135798642&0x7ffffff]=true;
	bloom[(x*135798642+y^987654321)*123456789&0x7ffffff]=true;
}
inline bool count(int x, int y){
	return bloom[(x*123456789+y^135798642)*987654321&0x7ffffff] and
		bloom[(x*987654321+y^123456789)*135798642&0x7ffffff] and
		bloom[(x*135798642+y^987654321)*123456789&0x7ffffff];
}
inline int readint(){
	int ret=0;
	for(char c;;){
		c=getchar_unlocked();
		if('0'<=c and c<='9')
			ret=ret*10+(c&15);
		else
			return ret;
	}
}
vector<char> digits;
inline void printint(int x){
	do{
		digits.push_back(x%10|48);
		x/=10;
	}while(x);
	while(not digits.empty())
		putchar(digits.back()), digits.pop_back();
}
int main(){
	digits.reserve(10);
	int n=readint(), m=readint();
	vector<vector<int>> adjLis(n);
	for(int i=m; i--;){
		int a=readint()-1, b=readint()-1;
		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){
					printint(ans.back()+1);
					putchar(' ');
					visited[ans.back()]=false;
					ans.pop_back();
				}
				printint(ans.back()+1);
				putchar('\n');
				visited[ans.back()]=false;
				ans.pop_back();
			}
			x=y;
		}
	}
}

Compilation message (stderr)

postmen.cpp: In function 'void insert(int, int)':
postmen.cpp:8:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    8 |  bloom[(x*123456789+y^135798642)*987654321&0x7ffffff]=true;
      |         ~~~~~~~~~~~^~
postmen.cpp:9:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    9 |  bloom[(x*987654321+y^123456789)*135798642&0x7ffffff]=true;
      |         ~~~~~~~~~~~^~
postmen.cpp:10:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   10 |  bloom[(x*135798642+y^987654321)*123456789&0x7ffffff]=true;
      |         ~~~~~~~~~~~^~
postmen.cpp: In function 'bool count(int, int)':
postmen.cpp:13:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   13 |  return bloom[(x*123456789+y^135798642)*987654321&0x7ffffff] and
      |                ~~~~~~~~~~~^~
postmen.cpp:14:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   14 |   bloom[(x*987654321+y^123456789)*135798642&0x7ffffff] and
      |          ~~~~~~~~~~~^~
postmen.cpp:15:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   15 |   bloom[(x*135798642+y^987654321)*123456789&0x7ffffff];
      |          ~~~~~~~~~~~^~

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