Submission #534071

#	Time	Username	Problem	Language	Result	Execution time	Memory
534071		colazcy	Rima (COCI17_rima)	C++17	56 / 140	1080 ms	65828 KiB

rima

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <vector>
#include <stack>
#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 = 5e5 + 10,maxm = 3e6 + maxn + 100,base = 131;

bool vis[maxn];
int siz[maxn],mem[maxn];
std::vector<int> G[maxn];
int dp(const int u){
	if(vis[u])return mem[u];
	// debug("siz[%d] = %d\n",u,siz[u]);
	vis[u] = true;
	int res = 0;
	for(let v : G[u])
		res = std::max(res,siz[u] + dp(v));
	return mem[u] = res + siz[u];
}
namespace tarjan{
	std::vector<int> G[maxn];
	void addedge(const int u,const int v){
		// debug("%d %d\n",u,v);
		G[u].push_back(v);}
	bool instk[maxn];
	int dfn[maxn],scc[maxn],scc_tot,dfs_tot;
	std::stack<int> stk;
	int tarjan(const int u){
		int low = dfn[u] = ++dfs_tot;
		stk.push(u); instk[u] = true;
		for(let v : G[u])
			if(!dfn[v])low = std::min(low,tarjan(v));
			else if(instk[v])low = std::min(low,dfn[v]);
		if(low == dfn[u]){
			scc_tot++;
			int t;
			do{
				t = stk.top(); stk.pop(),instk[t] = false;
				scc[t] = scc_tot;
				siz[scc_tot]++;
			}while(t != u);
		}
		return low;
	}
}
int n,len[maxn];
char buf[maxm],*now = buf,*str[maxn];
std::vector<std::pair<ull,int>> vec;
int find(const ull x){
	let it = std::lower_bound(vec.begin(),vec.end(),std::make_pair(x,0));
	if(it != vec.end() && it->first == x)return it->second;
	return -1;
}
int main(){
	// std::freopen("rima.in","r",stdin);
	// std::freopen("rima.out","w",stdout);
	std::scanf("%d",&n);
	rep(i,1,n){
		str[i] = now;
		std::scanf("%s",str[i]);
		len[i] = std::strlen(str[i]);
		now += len[i] + 1;
		std::reverse(str[i],str[i] + len[i]);
	}
	rep(id,1,n){
		ull h = 0;
		for(int i = 0;i < len[id];i++)h = h * base + str[id][i];
		vec.emplace_back(h,id);
	}
	std::sort(vec.begin(),vec.end());
	rep(id,1,n){
		ull h = 0;
		for(int i = 0;i < len[id] - 1;i++)h = h * base + str[id][i];
		let t = find(h);
		if(t != -1)tarjan::addedge(id,t);
		rep(c,'a','z'){
			let t = find(h * base + c);
			if(t != -1)tarjan::addedge(id,t);
		}
		h = h * base + str[id][len[id] - 1];
		rep(c,'a','z'){
			let t = find(h * base + c);
			if(t != -1)tarjan::addedge(id,t);
		}
	}
	rep(i,1,n)
		if(!tarjan::dfn[i])tarjan::tarjan(i);
	rep(u,1,n)
		for(let v : tarjan::G[u])
			if(tarjan::scc[u] != tarjan::scc[v])
				G[u].push_back(v);
	int ans = 0;
	// debug("%d\n",tarjan::scc_tot);
	rep(i,1,tarjan::scc_tot)
		ans = std::max(ans,dp(i));
	std::printf("%d\n",ans);
	// rep(i,1,n)debug("%s\n",str[i]);

	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 56 / 140