oj.uz

답안 #527667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527667 2022-02-18T00:32:13 Z colazcy Savez (COCI15_savez) C++11
120 / 120
 75 ms 16948 KB 
#include <cstdio>
#include <cassert>
#include <cstring>
#include <map>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ull = unsigned long long;
constexpr int maxn = 2e6 + 10,base = 229;

std::map<ull,int> mp;
bool vis[maxn];
int n,ans,ptr,len[maxn],pi[maxn];
char buf[maxn * 3],*str[maxn];
int main(){
	// std::freopen("savez.in","r",stdin);
	// std::freopen("savez.out","w",stdout);
	std::scanf("%d",&n);
	rep(i,1,n){
		str[i] = buf + ptr;
		std::scanf("%s",str[i] + 1);
		len[i] = std::strlen(str[i] + 1);
		ptr += len[i] + 2;
	}
	rep(id,1,n){
		let str = ::str[id];
		let len = ::len[id];
		int mx = 1,j = 0;
		rep(i,1,len)vis[i] = false;
		pi[1] = 0;
		rep(i,2,len){
			while(j && str[j + 1] != str[i])j = pi[j];
			if(str[j + 1] == str[i])j++;
			pi[i] = j;
		}
		int now = len;
		while(now)
			vis[now] = true,
			now = pi[now];
		ull s = 0;
		rep(i,1,len){
			s = s * base + str[i];
			if(vis[i]){
				let it = mp.find(s);
				if(it != mp.end())mx = std::max(mx,it->second + 1);				
			}
		}
		mp[s] = mx;
		ans = std::max(ans,mx);
	}
	std::printf("%d\n",ans);
	std::fclose(stdin);
	std::fclose(stdout);	
	return 0;
}

Compilation message

savez.cpp: In function 'int main()':
savez.cpp:21:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
savez.cpp:24:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   std::scanf("%s",str[i] + 1);
      |   ~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 296 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 436 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 2220 KB Output is correct
2 Correct 16 ms 2248 KB Output is correct
3 Correct 35 ms 2248 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 15 ms 2216 KB Output is correct
3 Correct 25 ms 2296 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2348 KB Output is correct
2 Correct 13 ms 2384 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2484 KB Output is correct
2 Correct 13 ms 2532 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2680 KB Output is correct
2 Correct 13 ms 2788 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 3280 KB Output is correct
2 Correct 18 ms 3276 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5668 KB Output is correct
2 Correct 26 ms 5700 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 8068 KB Output is correct
2 Correct 36 ms 8044 KB Output is correct
3 Correct 75 ms 16948 KB Output is correct