結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2020-02-08 04:35:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 371 ms / 1,000 ms |
コード長 | 684 bytes |
コンパイル時間 | 1,933 ms |
コンパイル使用メモリ | 196,684 KB |
最終ジャッジ日時 | 2025-01-08 22:55:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:7:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 7 | int N;scanf("%d%*c",&N); | ~~~~~^~~~~~~~~~~~ main.cpp:19:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 19 | int M;long long X,D;scanf("%d%lld%lld%*c",&M,&X,&D); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;int Trie[800001][26];int main(){int N;scanf("%d%*c",&N);int s=1;vector<vector<int>>d(N);for(int i=0;i<N;++i){int p=0;d[i].push_back(p);for(int c;c=getchar(),c!='\n';){c-='a';p=Trie[p][c]=Trie[p][c]?:s++;d[i].push_back(p);}}int M;long long X,D;scanf("%d%lld%lld%*c",&M,&X,&D);long long NN=N*(long long)(N-1),z=0;--N;for(int _=0;_<M;++_){int i=X/N,j=X%N;if(i>j){swap(i,j);}else{++j;}X+=D;if(X>=NN){X-=NN;}int ok=0,ng=min(d[i].size(),d[j].size());while(ng-ok>1){int k=ok+ng>>1;(d[i][k]==d[j][k]?ok:ng)=k;}z+=ok;}cout<<z<<"\n";return 0;}