Submission #527667

#	Time	Username	Problem	Language	Result	Execution time	Memory
527667		colazcy	Savez (COCI15_savez)	C++11	120 / 120	75 ms	16948 KiB

savez

#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 (stderr)

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12