oj.uz

답안 #396153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396153 2021-04-29T13:54:03 Z Nicholas_Patrick 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 449 ms 49588 KB 
#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

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.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 10 ms 14924 KB Output is correct
5 Correct 6 ms 9548 KB Output is correct
6 Correct 10 ms 16176 KB Output is correct
7 Correct 13 ms 16976 KB Output is correct
8 Correct 8 ms 13004 KB Output is correct
9 Correct 37 ms 18048 KB Output is correct
10 Correct 10 ms 14924 KB Output is correct
11 Correct 10 ms 14540 KB Output is correct
12 Correct 38 ms 18252 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 14924 KB Output is correct
5 Correct 7 ms 9548 KB Output is correct
6 Correct 10 ms 16224 KB Output is correct
7 Correct 13 ms 16972 KB Output is correct
8 Correct 10 ms 12996 KB Output is correct
9 Correct 36 ms 18124 KB Output is correct
10 Correct 9 ms 14976 KB Output is correct
11 Correct 9 ms 14540 KB Output is correct
12 Correct 38 ms 18308 KB Output is correct
13 Correct 66 ms 23268 KB Output is correct
14 Correct 56 ms 21280 KB Output is correct
15 Correct 57 ms 21052 KB Output is correct
16 Correct 66 ms 23240 KB Output is correct
17 Correct 67 ms 21116 KB Output is correct
18 Correct 67 ms 21472 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 9 ms 14928 KB Output is correct
5 Correct 6 ms 9424 KB Output is correct
6 Correct 10 ms 16144 KB Output is correct
7 Correct 13 ms 16888 KB Output is correct
8 Correct 8 ms 13004 KB Output is correct
9 Correct 35 ms 18116 KB Output is correct
10 Correct 9 ms 14924 KB Output is correct
11 Correct 9 ms 14428 KB Output is correct
12 Correct 40 ms 18244 KB Output is correct
13 Correct 70 ms 23236 KB Output is correct
14 Correct 57 ms 21284 KB Output is correct
15 Correct 59 ms 21128 KB Output is correct
16 Correct 69 ms 23248 KB Output is correct
17 Correct 66 ms 21060 KB Output is correct
18 Correct 65 ms 21392 KB Output is correct
19 Correct 431 ms 49584 KB Output is correct
20 Correct 358 ms 40540 KB Output is correct
21 Correct 356 ms 38764 KB Output is correct
22 Correct 429 ms 49588 KB Output is correct
23 Correct 142 ms 23080 KB Output is correct
24 Correct 449 ms 39272 KB Output is correct
25 Correct 441 ms 47308 KB Output is correct