12442 - Forwarding Emails

[brianfry713]

Your code is getting TLE.
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).

[nbacool2]

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;
vector<int> answers;
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];
}
void read()
{
    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;
        }
    }
    answers.push_back(node);
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        read();
    }
    for(int i = 0; i < T; ++i)
    {
        cout<<"Case "<<i+1<<": "<<answers[i];
        if(i < T-1) cout<<'\n';
    }
    return 0;
}

[lbv]

(..) 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]

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]

Always print a newline char at the end of the last line.

[LazyTym]

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;
vector<vector<int> >adjList(MAX);



int DFS_VIST(int n)
{
    time=time+1;
    int v;
    visited[n]=1;
    for(int i=0;i<adjList[n].size();i++) {
        v=adjList[n][i];
        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=0;i<=nVertex;i++) adjList[i].clear();
        for(int i=1;i<=nVertex;i++) {
            cin>>x>>y;
            adjList[x].push_back(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]

Next time post in the existing thread. Check "My Submissions" to see the reason for your CE.

[Repon kumar Roy]

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;
}

[brianfry713]

Don't read from a file.

[brianfry713]

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.

[ashdboss]

Getting wrong answer. Need help

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 READ freopen("input.txt", "r", stdin)
#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[105][105]; 
int d[105][105],vis[105][105];
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;
};
//vector<int>G[5];//graph adjacency list
int g[50005];
int sum[50005];
//graph G[50005];
int visited[50005]={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();
		{
			v = g[u];//adjacent node
			if(!visited[v] && v)
			{
				vc.push_back(v);
				visited[v] =1;
				sum[v]=sum[u]+1;
				Q.push(v);
			}
			else //already visited
			{
				//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[102],no_dependency,index_of_dependent;

	char ch,second[1000],first[1000];
	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]

Try the I/O in this thread.

[milesstevenson]

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.InputStreamReader;
import java.io.BufferedReader;
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;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task12442 solver = new Task12442();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task12442 {
    int G[] = new int[50000], depth[] = new int[50000], visited[] = new int[50000];
    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);

            // populate adjacency graph
            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));
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

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

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

[TryCatchMe]

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]

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.InputStreamReader;
import java.io.BufferedReader;
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;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task12442 solver = new Task12442();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task12442 {
    int G[] = new int[50000], depth[] = new int[50000], visited[] = new int[50000];
    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);

            // populate adjacency graph
            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));
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        } 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.