Recently I've tried to solve a problem of SPOj. After submitting the solution it is giving me WA. :(
I've tried with some cases and every input is giving me correct answer. But as the online judge is giving me "Wrong Answer" verdict, definitely my solution has a wrong. :/
Would anyone please give me a test case for which my code gives wrong output?
Here is problem link. My solution is given below:
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
using namespace std;
// Define Some Variables
#define eps 1e-14
#define si 100010
#define pi acos(-1.0)
#define inf (1<<30)-1
#define mod 1000000000 //10^9
//Define Some Functions
#define even(a) ((a)%2==0)
#define odd(a) ((a)%2==1)
#define max(a,b) (a>b ?a:b)
#define min(a,b) (a<b ?a:b)
#define pb push_back
#define mpair make_pair
#define sqr(a)((a)*(a))
#define area(x1,y1,x2,y2,x3,y3) (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)) //Area of a triangle
#define dist(x1,y1,x2,y2) (sqr(x1-x2)+sqr(y1-y2)) //Distance between two points
#define mem(a,v) memset(a,v,sizeof(a))
inline bool compare( double a, double b ) { return fabs( a-b ) < eps ; }
#define fr(i,a,b) for(i=a;i<=b;i++)
#define rep(i,a,b) for(i=a;i<b;i++)
#define rev(i,a,b) for(i=a;i>=b;i--)
typedef long long i64;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int i,j,l,n,cs=1,cnt_node;
char ch[si];
struct node
{
int nxt[26],fg;
}trie[si];
int BuildNode()
{
int i;
rep(i,0,26)
trie[cnt_node].nxt[i]=-1;
trie[cnt_node].fg=0;
return cnt_node++;
}
void insert()
{
int i,j,k=0;
rep(i,0,l)
{
j=ch[i]-65;
if(trie[k].nxt[j]<0)
trie[k].nxt[j]=BuildNode();
k=trie[k].nxt[j];
trie[k].fg++;
}
}
int query(int node,int ind)
{
if(ind==l)
return 0;
int j=ch[ind]-65,p=0,k;
if(trie[node].nxt[j]<0)
return 0;
k=trie[node].nxt[j];
if(k>=0&&trie[k].fg)
{
trie[k].fg--;
p=1+query(k,ind+1);
}
return p;
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int ans;
while(~scanf("%d",&n)&&n>=0)
{
cnt_node=0;
BuildNode();
fr(i,1,n)
{
scanf("%s",ch);
l=strlen(ch);
insert();
}
ans=0;
fr(i,1,n)
{
scanf("%s",ch);
l=strlen(ch);
ans+=query(0,0);
}
printf("%d\n",ans);
}
return 0;
}
Aucun commentaire:
Enregistrer un commentaire