## 12442 - Forwarding Emails

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12442 - Forwarding Emails

Create a test case with N=50000 and all Martians in a circle forwarding the email to the person on it's right. The output should be 1. My AC code handles that case on my machine in 0.026 sec, your code takes a long time (well over the 1 second limit).
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 12442 - Forwarding Emails

Hi, guys. I got the following code which I tested on all of the inputs in this topic and got the correct answers but I still get WA on the judge. Any ideas?

Code: Select all

``````#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 60000;
int parent[MAXN];
int child[MAXN];
int potential[MAXN];
bool visited[MAXN];
bool inCycle[MAXN];
int DFS(int root)
{
if(root == -1) return 0;
if(potential[root] != -1) return potential[root];
if(visited[root])
{
inCycle[root] = true;
return 0;
}
visited[root] = true;
potential[root] = 1 + DFS(child[root]);
if(inCycle[root])
{
int currentNode = child[root];
while(currentNode != root)
{
potential[currentNode] = potential[root];
currentNode = child[currentNode];
}
}
return potential[root];
}
{
memset(parent, -1, sizeof parent);
memset(child, -1, sizeof child);
memset(potential, -1, sizeof potential);
memset(visited, 0, sizeof visited);
memset(inCycle, 0, sizeof inCycle);
int N;
cin >> N;
for(int i = 0; i < N; ++i)
{
int from, to;
cin >> from >> to;
parent[to] = from;
child[from] = to;
}
int maxPotential = 0;
int node = 0;
for(int i = 1; i <= N; ++i)
{
if(!visited[i])
{
DFS(i);
}
if(maxPotential < potential[i])
{
maxPotential = potential[i];
node = i;
}
}
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
for(int i = 0; i < T; ++i)
{
}
for(int i = 0; i < T; ++i)
{
if(i < T-1) cout<<'\n';
}
return 0;
}``````

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 12442 - Forwarding Emails

nbacool2 wrote:(..) I still get WA on the judge. Any ideas?
Always print a newline at the end of a test case, including the last one.

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 12442 - Forwarding Emails

Damn, I just got 2 ACs on problems by printing a new line in the end . Thanks, man. But this means problem definitions for the output are misleading because sample outputs don't end with a new line, nor does the problem output formatting state it and that's the only reason I didn't put a new line.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12442 - Forwarding Emails

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### 12442 - Forwarding Emails.why compile error??

why getting compile error every time.............pls tell me about compile error........

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#define MAX 50010

using namespace std;
int nVertex;
int *visited,time;

int DFS_VIST(int n)
{
time=time+1;
int v;
visited[n]=1;
if(visited[v]==0) {
DFS_VIST(v);
//cout<<"time="<<time<<"  ";
}
}
return time;
}

int DFS(int n) {
visited=new int[nVertex+1];
time=0;
for(int i=1;i<=nVertex;i++) visited[i]=0;
return DFS_VIST(n);

}

int main()
{

int t,x,y,c=1;
cin>>t;
while(t--)
{
cin>>nVertex;
for(int i=1;i<=nVertex;i++) {
cin>>x>>y;
}
int maximum=0,t,solution=0;
for(int i=1;i<=nVertex;i++){
t=DFS(i);
if(maximum<t) {
maximum=t;
solution=i;
}

}
cout<<"Case "<<c<<": "<<solution<<endl;
c++;
}
return 0;

}

``````
thanks in advance. brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12442 - Forwarding Emails

Next time post in the existing thread. Check "My Submissions" to see the reason for your CE.
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 12442 - Forwarding Emails

I assumed u!=v
as The problem statement said
But getting WA,
Is there any input u==v

I was using big number of i/o using file. Now I commented them,
But This code also give WAs.

Code: Select all

``````

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
using namespace std;

/*------- Constants---- */
#define MX 50004
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)

/* -------Global Variables ------ */
ll x,y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))

/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ T t; if(b==0){d = a;x=1;y=0;} else {extended_euclid_returning_gcd(b, a%b); t=x; x=y;y = t-(a*y/b);}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}

int touch[MX], arr[MX], dp[MX];

vector<int> tmp;
int endVal;
int flag = 0;
int before;
int why = 0;

void call ( int n , int cnt)
{

if(touch[n]== 1) {
endVal = n;
flag = 1;
return ;
}
if( dp[n] !=-1) return;
else {

touch[n] = 1;

if( dp[arr[n]] != -1)  {
before = cnt + dp[arr[n]] + 1;

return;
}

call(arr[n] , cnt+1);
if(  flag ) tmp.push_back(n);

if( endVal == n ) {
flag = 0;
before = cnt  + (int )(tmp.size());
}
}
return;
}
int main()
{

int test , n, i , maximum , a, b , cs  =0 ,messe;
//freopen("in.txt", "r", stdin);
cin >> test ;

while (test --) {
cin >> n ;
ms(dp, -1);
ms(touch, 0);
for( int i = 0 ; i < n ; i++ ){
cin >> a >> b;

arr[a] = b;
if( a == b ) {
dp[a] = 1;
//printf("Wrong Input\n");
}
}
maximum = 0 ;
for( int i = 1; i <= n ; i ++){

if( dp[i] ==-1) {
call(i , 0 );
dp[i] = before;

}
for (int j = 0; j < tmp.size(); j ++ ) {
if(dp[tmp[j]]==-1)  dp[tmp[j]] =( int)  tmp.size();
}
if( dp[i] > maximum){
maximum = dp[i];
messe = i;
}
tmp.clear();

}

printf("Case %d: %d\n",++cs, messe);
}
return 0;
}
``````
Last edited by Repon kumar Roy on Thu Oct 30, 2014 11:31 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12442 - Forwarding Emails

Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12442 - Forwarding Emails

Try the I/O in this thread. Next time make a new post when editing your code so that it's clear that you've changed it.
Check input and AC output for thousands of problems on uDebug!

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

### Re: 12442 - Forwarding Emails

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
#include <queue>
#include<string>
#include<cstring>
#include<sstream>
#include<list>
#include<math.h>
#include<map>
#include<set>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define PB push_back
#define PI acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

#define WRITE freopen("output.txt", "w", stdout)

#define LL long long
#define MOD 1000000007
#define MX 100010

#define pii pair<int,int>
int fx[]={1,-1,0,0,1,1,-1,-1};
int fy[]={0,0,1,-1,1,-1,1,-1};

char cell;
int d,vis;
int row,col;

int check(int tx,int ty)
{

if(tx>=0 && tx<row && ty>=0 && ty<col)
return 1;

return 0;
}
struct graph{
int x;
int y;
};
int g;
int sum;
//graph G;
int visited={0};
vector<int>vc;
int bfs(int n,int src){
queue<int>Q;
int total =0,u;
Q.push(src);
int v;
visited[src]=1;
sum[src]=1;
while(!Q.empty())
{
u = Q.front();
{
if(!visited[v] && v)
{
vc.push_back(v);
visited[v] =1;
sum[v]=sum[u]+1;
Q.push(v);
}
{
//if(v==0)
//	return sum[u];
if (v == src)
return sum[u]+1;
return sum[u]+sum[v];//sum[src]+sum[v]
}
}
Q.pop();
}
//return sum[v];
}
int main()
{

int n,m,x,y,i,j,k;
int no_of_prior,no_dependency,index_of_dependent;

char ch,second,first;
string str;
int test_case=0;
int number;
/*freopen ("d:/input.txt","w",stdout);
for(i=1;i<50000;i++)
{
printf("%d %d\n",i,i+1);
}*/
scanf("%d",&test_case);
for(k=1;k<=test_case;k++)
{
scanf("%d",&n);
vc.clear();
memset(sum,0,sizeof(sum));
memset(visited,0,sizeof(visited));
memset(g,0,sizeof(g));
i=0;
while(i<n)
{
scanf("%d%d",&x,&y);
g[x] =y;
i++;
}

int ans =1;
int max =-1;
for(i=1;i<=n;i++)
{
if(visited[i]==0 && g[i])
{
sum[i] = bfs(n,i);
if(sum[i]>=max)
{
max = sum[i];
ans =i;
/*if(max == n)
break;*/
}
for(j=0;j<vc.size();j++)
sum[vc[j]] = sum[i];
vc.clear();
}
}

printf("Case %d: %d\n",k,ans);

}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12442 - Forwarding Emails

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

milesstevenson
New poster
Posts: 10
Joined: Sat Oct 11, 2014 2:47 pm

### Re: 12442 - Forwarding Emails

Hi. Could anyone please help me understand why I'm getting TLE for this problem when I pass all test data provided here. I am using Java and have done re-factoring on the code a few times now. Really starting to feel down about it. Any help would be appreciated. Thank you.

Code: Select all

``````import java.util.Arrays;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Miles Stevenson
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
solver.solve(1, in, out);
out.close();
}
}

int G[] = new int, depth[] = new int, visited[] = new int;
int T, maxDepth, maxDepthNode;

public int dfs(int u) {
int v = G[u];
int r = 0;
visited[u] = 1;
if (visited[v] == 0)
r = dfs(v) + 1;
visited[u] = 0;
depth[u] = r;
return r;
}

public void solve(int testNumber, InputReader in, PrintWriter out) {
T = in.nextInt();

// iterate each test case
for (int testCase = 0; testCase < T; testCase++) {
int totalNodes = in.nextInt();
maxDepth = 0;
Arrays.fill(G, 0);
Arrays.fill(visited, 0);
Arrays.fill(depth, -1);

for (int i = 0; i < totalNodes; i++) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
G[u] = v;
}

// iterate over each vertex with a dfs call
for (int i = 0; i < totalNodes; i++) {
if (depth[i] == -1)
dfs(i);
if (depth[i] > maxDepth) {
maxDepth = depth[i];
maxDepthNode = i;
}
else if (depth[i] == maxDepth && i < maxDepthNode)
maxDepthNode = i;
}

// print final data for test case
out.println("Case " + (testCase+1) + ": " + (maxDepthNode+1));
}
}
}

private StringTokenizer tokenizer;

tokenizer = null;
}

public String nextLine() {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}

public String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(nextLine());
}
} catch (NullPointerException e) {
return null;
}
}

public int nextInt() {
return Integer.parseInt(next());
}
}

``````

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

### Re: 12442 - Forwarding Emails

brianfry713 wrote:Input:

Code: Select all

``````10
22
1 15
2 19
3 9
4 11
5 10
6 17
7 19
8 19
9 6
10 4
11 17
12 1
13 18
14 11
15 9
16 3
17 9
18 12
19 9
20 4
21 1
22 22
16
1 15
2 15
3 13
4 4
5 9
6 9
7 3
8 3
9 7
10 11
11 2
12 9
13 2
14 6
15 9
16 4
22
1 2
2 11
3 5
4 17
5 21
6 11
7 20
8 5
9 22
10 6
11 7
12 1
13 5
14 1
15 15
16 12
17 15
18 8
19 20
20 17
21 2
22 20
22
1 12
2 5
3 13
4 9
5 5
6 12
7 1
8 11
9 11
10 9
11 14
12 6
13 5
14 2
15 3
16 9
17 2
18 6
19 15
20 22
21 10
22 15
27
1 13
2 20
3 2
4 3
5 6
6 18
7 24
8 5
9 15
10 15
11 10
12 2
13 27
14 8
15 6
16 1
17 7
18 11
19 13
20 13
21 2
22 25
23 27
24 16
25 17
26 10
27 16
2
1 1
2 1
19
1 5
2 9
3 4
4 8
5 5
6 8
7 14
8 17
9 3
10 6
11 5
12 16
13 17
14 11
15 5
16 5
17 7
18 15
19 10
18
1 5
2 4
3 17
4 18
5 10
6 15
7 14
8 4
9 3
10 10
11 16
12 18
13 14
14 17
15 10
16 13
17 2
18 5
6
1 2
2 5
3 3
4 1
5 3
6 4
16
1 1
2 1
3 13
4 16
5 11
6 3
7 12
8 13
9 11
10 5
11 4
12 14
13 14
14 14
15 5
16 11
``````
AC output:

Code: Select all

``````Case 1: 13
Case 2: 10
Case 3: 18
Case 4: 21
Case 5: 22
Case 6: 2
Case 7: 2
Case 8: 11
Case 9: 6
Case 10: 10
``````
Brianfry (the legendary Brianfry!), there won't be any cases such as 1, 4 and 10 because no person emails themselves. Directly from the problem description: "Instead of just forwarding them willy-nilly, or not at all, they each pick one other person they know to email those things to every time - exactly one, no less, no more (and never themselves)". My code failed for these cases (and cases 4, 16 and 20 from the random input on uDebug) but I got ACC using DFS with cycle checking. Using BFS will definitely get you TLE as I found out.

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

### Re: 12442 - Forwarding Emails

milesstevenson wrote:Hi. Could anyone please help me understand why I'm getting TLE for this problem when I pass all test data provided here. I am using Java and have done re-factoring on the code a few times now. Really starting to feel down about it. Any help would be appreciated. Thank you.

Code: Select all

``````import java.util.Arrays;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Miles Stevenson
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
solver.solve(1, in, out);
out.close();
}
}

int G[] = new int, depth[] = new int, visited[] = new int;
int T, maxDepth, maxDepthNode;

public int dfs(int u) {
int v = G[u];
int r = 0;
visited[u] = 1;
if (visited[v] == 0)
r = dfs(v) + 1;
visited[u] = 0;
depth[u] = r;
return r;
}

public void solve(int testNumber, InputReader in, PrintWriter out) {
T = in.nextInt();

// iterate each test case
for (int testCase = 0; testCase < T; testCase++) {
int totalNodes = in.nextInt();
maxDepth = 0;
Arrays.fill(G, 0);
Arrays.fill(visited, 0);
Arrays.fill(depth, -1);

for (int i = 0; i < totalNodes; i++) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
G[u] = v;
}

// iterate over each vertex with a dfs call
for (int i = 0; i < totalNodes; i++) {
if (depth[i] == -1)
dfs(i);
if (depth[i] > maxDepth) {
maxDepth = depth[i];
maxDepthNode = i;
}
else if (depth[i] == maxDepth && i < maxDepthNode)
maxDepthNode = i;
}

// print final data for test case
out.println("Case " + (testCase+1) + ": " + (maxDepthNode+1));
}
}
}

private StringTokenizer tokenizer;

tokenizer = null;
}

public String nextLine() {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}

public String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(nextLine());
}
} catch (NullPointerException e) {
return null;
}
}

public int nextInt() {
return Integer.parseInt(next());
}
}

``````
First of all you aren't taking into account cycles. This may be why you are getting TLE. What about this test case?

Code: Select all

``````1
7
2 4
4 1
1 3
3 4
5 3
6 2
7 4
``````
Output

Code: Select all

``````6
``````
Secondly, not that this is making any time difference but the following else if (depth == maxDepth && i < maxDepthNode)

Code: Select all

``````for (int i = 0; i < totalNodes; i++) {
if (depth[i] == -1)
dfs(i);
if (depth[i] > maxDepth) {
maxDepth = depth[i];
maxDepthNode = i;
}
else if (depth[i] == maxDepth && i < maxDepthNode)
maxDepthNode = i;
}
``````
never gets executed since if you found an equal depth you would already have the smaller vertex in an earlier iteration... this is because i can only get larger (i++) and the answer wants the smallest.

Thirdly, reconsider your i/o routines. Why not have a much more compact i/o process that involves no casting, etc?

Code: Select all

``````Scanner sc = new Scanner(System.in);
int numCases = sc.nextInt();

for (int i = 1; i <= numCases; i++) {
int numNodes = sc.nextInt(), src, dst;

for (int i = 0; i < numNodes; i++) {
src = sc.nextInt();
dst = sc.nextInt();
//process the edge [src, dst]
}
//process
System.out.println("Case " + i + ": " + yourSolutionHere);
}
sc.close();
``````
Hope this helps my friend.