| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 223278 |
2020-04-15T06:35:40 Z |
jamielim |
Trener (COCI20_trener) |
C++14 |
|
9 ms |
2816 KB |
#include <bits/stdc++.h>
using namespace std;
/*
#define mp make_pair
const int MAXN=200005;
int n;
vector<int> adj[MAXN];
int sub[MAXN];
int depth[MAXN];
int heavy[MAXN];
int pos[MAXN];
int head[MAXN];
int par[MAXN];
int cur=1;
struct node{
int s,e,m;long long v,lazy;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;v=lazy=0;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void laze(){
if(s==e){v^=lazy;lazy=0;return;}
v^=lazy;
l->lazy+=lazy;r->lazy+=lazy;
lazy=0;return;
}
void upd(int x,int y,long long nv){
//printf("u %d %d\n",x,y);
if(x>y)return;
if((s==x&&e==y)||s==e){
lazy^=nv;laze();return;
}
if(y<=m)l->upd(x,y,nv);
else if(x>m)r->upd(x,y,nv);
else{l->upd(x,m,nv);r->upd(m+1,y,nv);}
laze();
v=l->v+r->v;
}
long long qry(int x,int y){
//printf("q %d %d\n",x,y);
if(x>y)return 0;
laze();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return l->qry(x,m)^r->qry(m+1,y);
}
}*root;
void dfs(int x,int p){
sub[x]=1;par[x]=p;int maxc=0;
for(int i=0;i<(int)adj[x].size();i++){
if(adj[x][i]!=p){
depth[adj[x][i]]=depth[x]+1;
dfs(adj[x][i],x);
sub[x]+=sub[adj[x][i]];
if(sub[adj[x][i]]>maxc){maxc=sub[adj[x][i]];heavy[x]=adj[x][i];}
}
}
}
void dcmp(int x,int h){
head[x]=h;pos[x]=cur++;
if(heavy[x]!=-1)dcmp(heavy[x],h);
for(int i=0;i<(int)adj[x].size();i++){
if(heavy[x]==adj[x][i])continue;
if(par[x]==adj[x][i])continue;
dcmp(adj[x][i],adj[x][i]);
}
}
void upd(int a,int b,long long nv){
//printf("%d %d\n",a,b);
if(depth[a]>depth[b])swap(a,b);
for(;head[a]!=head[b];b=par[head[b]]){
if(depth[head[a]]>depth[head[b]])swap(a,b);
root->upd(pos[head[b]],pos[b],nv);
}
if(depth[a]>depth[b])swap(a,b);
root->upd(pos[a]+1,pos[b],nv);
}
long long qry(int a,int b){
long long res=0;
if(depth[a]>depth[b])swap(a,b);
for(;head[a]!=head[b];b=par[head[b]]){
if(depth[head[a]]>depth[head[b]])swap(a,b);
res+=root->qry(pos[head[b]],pos[b]);
}
if(depth[a]>depth[b])swap(a,b);
res+=root->qry(pos[a]+1,pos[b]);
return res;
}
int main(){
int q;
scanf("%d",&q);
pair<int,int> qu[q];
char op[10];int a,b;
n=1;
for(int i=0;i<q;i++){
scanf("%s%d%d",op,&a,&b);
if(op[0]=='A'){qu[i]=mp(a,b);n++;adj[a].push_back(b);adj[b].push_back(a);}
else qu[i]=mp(a,b);
}
root=new node(0,n);
memset(heavy,-1,sizeof(heavy));memset(par,-1,sizeof(par));
dfs(1,0);
dcmp(1,1);
//
int a,b,c1,c2;
for(int i=0;i<n-1;i++){
scanf("%d%d%d%d",&a,&b,&c1,&c2);a--;b--;
adj[a].push_back(b);adj[b].push_back(a);
edge[i]=mp(mp(a,b),mp(c1,c2));
}
root=new node(0,n);
memset(heavy,-1,sizeof(heavy));
memset(par,-1,sizeof(par));
dfs(0,-1);
dcmp(0,0);
for (int i =1; i <20; i ++) {
for (int j =0; j < n ; j ++) {
if( par[ j ][i-1]== -1) par[ j ][ i ]= -1;
else par[ j ][ i ]= par[ par[ j ][i-1]][i-1];
}
}
//for(int i=0;i<n;i++)printf("%d ",pos[i]);printf("\n");
for(int i=0;i<n-1;i++){
upd(i,i+1);
}
long long ans=0;
for(int i=0;i<n-1;i++){
int a=edge[i].first.first,b=edge[i].first.second;
long long cur=qry(a,b);
//printf("%d %d %lld\n",a,b,cur);
ans+=min(cur*edge[i].second.first,edge[i].second.second);
}
printf("%lld",ans);
}
*/
typedef long long ll;
const ll MOD=1000000007;
string str[20][1505];
vector<pair<string,int> > str2[20];
int main(){
int n,k;
scanf("%d%d",&n,&k);
char temp[55];
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++)str[i][j]='\0';
for(int j=0;j<k;j++){
scanf("%s",temp);
str[i][j]=temp;
}
sort(str[i],str[i]+k);
if(i!=0){
for(int j=0;j<k;j++){
string a,b;
for(int l=0;l<i;l++){
a+=str[i][j][l];
b+=str[i][j][l+1];
}
if(a==b)str2[i].push_back(make_pair(a,j));
else{str2[i].push_back(make_pair(a,j));str2[i].push_back(make_pair(b,j));}
}
sort(str2[i].begin(),str2[i].end());
//for(int j=0;j<2*k;j++)printf("%s ",str2[i][j].first.c_str());printf("\n");
}
}
ll dp[2][k]; memset(dp,0,sizeof(dp));
for(int i=0;i<k;i++)dp[1][i]=1;
for(int i=n-2;i>=0;i--){
int ptr=0;
int i1=i+1;
for(int j=0;j<k;j++){
if(j>0&&str[i][j]==str[i][j-1]){
dp[0][j]=dp[0][j-1];continue;
}
while(ptr<(int)str2[i1].size()){
if(str[i][j]==str2[i1][ptr].first){
dp[0][j]+=dp[1][str2[i1][ptr].second];
dp[0][j]%=MOD;
}else if(str[i][j]<str2[i1][ptr].first)break;
ptr++;
}
}
for(int j=0;j<k;j++){dp[1][j]=dp[0][j];dp[0][j]=0;}
}
ll ans=0;
for(int i=0;i<k;i++){ans+=dp[1][i];ans%=MOD;}
printf("%lld",ans);
}
Compilation message
trener.cpp: In function 'int main()':
trener.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
trener.cpp:160:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",temp);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 5 |
Runtime error |
9 ms |
2816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
