12442 - Forwarding Emails
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12442 - Forwarding Emails
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).
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!
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;
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;
}
Re: 12442 - Forwarding Emails
Always print a newline at the end of a test case, including the last one.nbacool2 wrote:(..) I still get WA on the judge. Any ideas?
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.
![:)](./images/smilies/icon_smile.gif)
-
- 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!
12442 - Forwarding Emails.why compile error??
why getting compile error every time.............pls tell me about compile error........
thanks in advance. ![:-?](./images/smilies/icon_confused.gif)
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;
}
![:-?](./images/smilies/icon_confused.gif)
-
- 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!
-
- 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.
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.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12442 - Forwarding Emails
Don't read from a file.
Check input and AC output for thousands of problems on uDebug!
-
- 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!
Re: 12442 - Forwarding Emails
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;
}
-
- 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!
-
- 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.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());
}
}
-
- New poster
- Posts: 15
- Joined: Fri May 30, 2014 12:09 am
Re: 12442 - Forwarding Emails
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.brianfry713 wrote:Input:AC output: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
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
-
- New poster
- Posts: 15
- Joined: Fri May 30, 2014 12:09 am
Re: 12442 - Forwarding Emails
First of all you aren't taking into account cycles. This may be why you are getting TLE. What about this test case?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.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()); } }
Code: Select all
1
7
2 4
4 1
1 3
3 4
5 3
6 2
7 4
Code: Select all
6
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;
}
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();