336

brianfry713 · Post by **brianfry713** » Tue Nov 20, 2012 12:02 am

The node numbers can be any integer, maybe greater than 100000, use a map.

@ce · Post by **@ce** » Tue Nov 27, 2012 6:25 am

Thanks brianfry, i got AC in Floyd-Warshal.

I tried the same question using BFS, getting RE, plzz help me..

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>

#define L long long int
#define U unsigned long long int
using namespace std;

map <int,int>m;
vector <int>v[111];
queue <pair <int,int> >q;
map<int, int> visit;

main()
{
      int n,t = 1;
      while(1)
      {
            cin>>n;
            m.clear();
            for(int i = 0;i<n;i++)
                  v[i].clear();
            if(n == 0)
                  break;
            int x = 0;
            for(int i = 0;i<n;i++)
            {
                  int a,b;
                  cin>>a>>b;
                  if(m.find(a) == m.end())
                        m.insert(make_pair (a,x++));
                  if(m.find(b) == m.end())
                        m.insert(make_pair (b,x++));
                  v[m.find(a)->second].push_back(b);
                  v[m.find(b)->second].push_back(a);
            }
            int start, ttl;
            while(1)
            {
                  cin>>start>>ttl;
                  int c = 0;
                  int y = 0;
                  if(!(start|ttl))
                        break;
                  while(!q.empty())
                        q.pop();
                  q.push(make_pair(start, 0));
                  visit.clear();
                  visit.insert(make_pair(start, y++));
                  while(1)
                  {
                        int node = q.front().first;
                        int d = q.front().second;
                        //cout<<node<<" ";
                        if(d > ttl)
                              break;
                        q.pop();
                        c++;
                        int key = m.find(node)->second;
                        for(int i = 0; i<v[key].size();i++)
                        {
                              if(visit.find(v[key][i]) != visit.end())
                                    continue;
                              visit.insert(make_pair(v[key][i], y++));
                              q.push(make_pair(v[key][i], d+1));
                        }

                  }
                  printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",t++,(x-c),start,ttl);
            }
      }
}

alimbubt · Post by **alimbubt** » Tue Dec 18, 2012 7:22 pm

brianfry713 wrote:Input
Code: Select all
2
1 1  1 2
1 1  0 0

0
Correct output:
Code: Select all
Case 1: 0 nodes not reachable from node 1 with TTL = 1.

Now my code gives Correct Answer for this input...But again WA......Please help
My edited code is

Code: Select all

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<bitset>
#include<string>
#include <sstream>
#include <fstream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define pi 2*acos(0.0)
using namespace std;

int BFS(int start,int ttl);
vector<int>adj[40];
vector<int>vec;
map<int,int>mp;

int main()
{
    int nc,node,i,f,u,v,j,start,ttl,t=0;
    while(scanf("%d",&nc)==1)
    {
        if(nc==0) break;
        f=0;
        for(i=1;i<=nc;i++)
        {
            scanf("%d%d",&u,&v);
            if(u==v) continue;
            if(mp[u]==0)
            {
                mp[u]=++f;
                vec.push_back(mp[u]);
            }
            if(mp[v]==0)
            {
                mp[v]=++f;
                vec.push_back(mp[v]);
            }
            adj[mp[u]].push_back(mp[v]);
            adj[mp[v]].push_back(mp[u]);
         }
        sort(vec.begin(),vec.end());
        node=vec.size();
        while(scanf("%d%d",&start,&ttl)==2)
        {
            int count;
            if(start==0&&ttl==0) break;
            int start1=start;
            if(mp[start]==0)
            {
                printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size(),start1,ttl);
                continue;
            }
            start=mp[start];
            count=BFS(start,ttl);
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++t,vec.size()-count,start1,ttl);
        }
        for(i=1;i<=node;i++)
        adj[i].clear();
        vec.clear();
        mp.clear();
    }
    return 0;
}


int BFS(int start,int ttl)
{
    int dist[50]={0};
    int count=1,i;
    map<int,int>mpp;
    mpp[start]=1;
    queue<int>q;
    q.push(start);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i];
            dist[v]=dist[u]+1;
            mpp[v]++;
            if(mpp[v]>1) continue;
            if(dist[v]<=ttl)
            count++;
            if(dist[v]<=ttl-1)
            q.push(v);
        }
    }
    mpp.clear();
    return count;
}

brianfry713 · Post by **brianfry713** » Thu Dec 20, 2012 12:09 am

Input:

Code: Select all

16
10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65
15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65
35  2  35  3   0  0

14
1 2  2 7  1 3  3 4  3 5  5 10  5 11
4 6  7 6  7 8  7 9  8 9  8  6  6 11
1 1  1 2  3 2  3 3  0 0
16
10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65
15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65
35  2  35  3   1  3   0  0

16
1 2  2 7  1 3  3 4  3 5  5 10  5 11
4 6  7 6  7 8  7 9  8 9  8  6  6 11 21 22 22 23
1 1  1 2  3 2  3 3  21 1 0 0

1
1 3
2 0
0 0

1
1 1
1 0
0 0
 
4
1 2 2 3 4 5 5 6
1 5 1 1 4 2 0 0

4
1 2
2 3
3 4
1 4
1 1
1 2
1 3
1 0
0 0


5
1 2 2 3 3 1 4 5 6 2147483647
1 1 1 0 4 1 4 2 5 1 6 2 8 2 0 0

10
1 2 1 3 3 5 2 5 3 4 5 4 6 4 7 10 10 9 8 9
2 3 7 2 10 1 0 0
 
4
0 0 1 2 2 3 4 4
1 0 1 1 1 2 1 3 1 4 2 0 2 1 2 2 2 3 2 4 3 0 3 1 3 2 3 3 4 0 4 1 4 2
0 0
 
30
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1
11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 1
21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16
1 17 1 18 1 19 1 20 1 21 18 0 18 1 18 2 18 3 18 4 18 5 18 6 18 7 18 8 18 9
18 10 18 11 18 12 18 13 18 14 18 15 0 0
32
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1 5 14 24 13
11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 1
21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16
1 17 1 18 1 19 1 20 1 21 18 0 18 1 18 2 18 3 18 4 18 5 18 6 18 7 18 8 18 9
18 10 18 11 18 12 18 13 18 14 18 15 0 0
3
1 2 2 3 4 5
1 0 1 1 1 2 1 3 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 5 0 5 1 5 2 5 3
0 0
 
1
10 11
10 0 10 1 10 2 12 1 10 0 10 1 10 2 0 0
0

Correct output:

Code: Select all

Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
Case 7: 5 nodes not reachable from node 35 with TTL = 2.
Case 8: 1 nodes not reachable from node 35 with TTL = 3.
Case 9: 3 nodes not reachable from node 1 with TTL = 3.
Case 10: 11 nodes not reachable from node 1 with TTL = 1.
Case 11: 8 nodes not reachable from node 1 with TTL = 2.
Case 12: 6 nodes not reachable from node 3 with TTL = 2.
Case 13: 4 nodes not reachable from node 3 with TTL = 3.
Case 14: 12 nodes not reachable from node 21 with TTL = 1.
Case 15: 1 nodes not reachable from node 2 with TTL = 0.
Case 16: 0 nodes not reachable from node 1 with TTL = 0.
Case 17: 3 nodes not reachable from node 1 with TTL = 5.
Case 18: 4 nodes not reachable from node 1 with TTL = 1.
Case 19: 3 nodes not reachable from node 4 with TTL = 2.
Case 20: 1 nodes not reachable from node 1 with TTL = 1.
Case 21: 0 nodes not reachable from node 1 with TTL = 2.
Case 22: 0 nodes not reachable from node 1 with TTL = 3.
Case 23: 3 nodes not reachable from node 1 with TTL = 0.
Case 24: 4 nodes not reachable from node 1 with TTL = 1.
Case 25: 6 nodes not reachable from node 1 with TTL = 0.
Case 26: 5 nodes not reachable from node 4 with TTL = 1.
Case 27: 5 nodes not reachable from node 4 with TTL = 2.
Case 28: 5 nodes not reachable from node 5 with TTL = 1.
Case 29: 5 nodes not reachable from node 6 with TTL = 2.
Case 30: 4 nodes not reachable from node 8 with TTL = 2.
Case 31: 4 nodes not reachable from node 2 with TTL = 3.
Case 32: 7 nodes not reachable from node 7 with TTL = 2.
Case 33: 7 nodes not reachable from node 10 with TTL = 1.
Case 34: 4 nodes not reachable from node 1 with TTL = 0.
Case 35: 3 nodes not reachable from node 1 with TTL = 1.
Case 36: 2 nodes not reachable from node 1 with TTL = 2.
Case 37: 2 nodes not reachable from node 1 with TTL = 3.
Case 38: 2 nodes not reachable from node 1 with TTL = 4.
Case 39: 4 nodes not reachable from node 2 with TTL = 0.
Case 40: 2 nodes not reachable from node 2 with TTL = 1.
Case 41: 2 nodes not reachable from node 2 with TTL = 2.
Case 42: 2 nodes not reachable from node 2 with TTL = 3.
Case 43: 2 nodes not reachable from node 2 with TTL = 4.
Case 44: 4 nodes not reachable from node 3 with TTL = 0.
Case 45: 3 nodes not reachable from node 3 with TTL = 1.
Case 46: 2 nodes not reachable from node 3 with TTL = 2.
Case 47: 2 nodes not reachable from node 3 with TTL = 3.
Case 48: 4 nodes not reachable from node 4 with TTL = 0.
Case 49: 4 nodes not reachable from node 4 with TTL = 1.
Case 50: 4 nodes not reachable from node 4 with TTL = 2.
Case 51: 29 nodes not reachable from node 1 with TTL = 0.
Case 52: 25 nodes not reachable from node 1 with TTL = 1.
Case 53: 21 nodes not reachable from node 1 with TTL = 2.
Case 54: 17 nodes not reachable from node 1 with TTL = 3.
Case 55: 13 nodes not reachable from node 1 with TTL = 4.
Case 56: 10 nodes not reachable from node 1 with TTL = 5.
Case 57: 8 nodes not reachable from node 1 with TTL = 6.
Case 58: 6 nodes not reachable from node 1 with TTL = 7.
Case 59: 4 nodes not reachable from node 1 with TTL = 8.
Case 60: 2 nodes not reachable from node 1 with TTL = 9.
Case 61: 0 nodes not reachable from node 1 with TTL = 10.
Case 62: 0 nodes not reachable from node 1 with TTL = 11.
Case 63: 0 nodes not reachable from node 1 with TTL = 12.
Case 64: 0 nodes not reachable from node 1 with TTL = 13.
Case 65: 0 nodes not reachable from node 1 with TTL = 14.
Case 66: 0 nodes not reachable from node 1 with TTL = 15.
Case 67: 0 nodes not reachable from node 1 with TTL = 16.
Case 68: 0 nodes not reachable from node 1 with TTL = 17.
Case 69: 0 nodes not reachable from node 1 with TTL = 18.
Case 70: 0 nodes not reachable from node 1 with TTL = 19.
Case 71: 0 nodes not reachable from node 1 with TTL = 20.
Case 72: 0 nodes not reachable from node 1 with TTL = 21.
Case 73: 29 nodes not reachable from node 18 with TTL = 0.
Case 74: 27 nodes not reachable from node 18 with TTL = 1.
Case 75: 25 nodes not reachable from node 18 with TTL = 2.
Case 76: 23 nodes not reachable from node 18 with TTL = 3.
Case 77: 19 nodes not reachable from node 18 with TTL = 4.
Case 78: 15 nodes not reachable from node 18 with TTL = 5.
Case 79: 11 nodes not reachable from node 18 with TTL = 6.
Case 80: 7 nodes not reachable from node 18 with TTL = 7.
Case 81: 5 nodes not reachable from node 18 with TTL = 8.
Case 82: 4 nodes not reachable from node 18 with TTL = 9.
Case 83: 3 nodes not reachable from node 18 with TTL = 10.
Case 84: 2 nodes not reachable from node 18 with TTL = 11.
Case 85: 1 nodes not reachable from node 18 with TTL = 12.
Case 86: 0 nodes not reachable from node 18 with TTL = 13.
Case 87: 0 nodes not reachable from node 18 with TTL = 14.
Case 88: 0 nodes not reachable from node 18 with TTL = 15.
Case 89: 29 nodes not reachable from node 1 with TTL = 0.
Case 90: 25 nodes not reachable from node 1 with TTL = 1.
Case 91: 21 nodes not reachable from node 1 with TTL = 2.
Case 92: 17 nodes not reachable from node 1 with TTL = 3.
Case 93: 13 nodes not reachable from node 1 with TTL = 4.
Case 94: 9 nodes not reachable from node 1 with TTL = 5.
Case 95: 6 nodes not reachable from node 1 with TTL = 6.
Case 96: 4 nodes not reachable from node 1 with TTL = 7.
Case 97: 2 nodes not reachable from node 1 with TTL = 8.
Case 98: 1 nodes not reachable from node 1 with TTL = 9.
Case 99: 0 nodes not reachable from node 1 with TTL = 10.
Case 100: 0 nodes not reachable from node 1 with TTL = 11.
Case 101: 0 nodes not reachable from node 1 with TTL = 12.
Case 102: 0 nodes not reachable from node 1 with TTL = 13.
Case 103: 0 nodes not reachable from node 1 with TTL = 14.
Case 104: 0 nodes not reachable from node 1 with TTL = 15.
Case 105: 0 nodes not reachable from node 1 with TTL = 16.
Case 106: 0 nodes not reachable from node 1 with TTL = 17.
Case 107: 0 nodes not reachable from node 1 with TTL = 18.
Case 108: 0 nodes not reachable from node 1 with TTL = 19.
Case 109: 0 nodes not reachable from node 1 with TTL = 20.
Case 110: 0 nodes not reachable from node 1 with TTL = 21.
Case 111: 29 nodes not reachable from node 18 with TTL = 0.
Case 112: 27 nodes not reachable from node 18 with TTL = 1.
Case 113: 25 nodes not reachable from node 18 with TTL = 2.
Case 114: 23 nodes not reachable from node 18 with TTL = 3.
Case 115: 19 nodes not reachable from node 18 with TTL = 4.
Case 116: 14 nodes not reachable from node 18 with TTL = 5.
Case 117: 8 nodes not reachable from node 18 with TTL = 6.
Case 118: 3 nodes not reachable from node 18 with TTL = 7.
Case 119: 1 nodes not reachable from node 18 with TTL = 8.
Case 120: 0 nodes not reachable from node 18 with TTL = 9.
Case 121: 0 nodes not reachable from node 18 with TTL = 10.
Case 122: 0 nodes not reachable from node 18 with TTL = 11.
Case 123: 0 nodes not reachable from node 18 with TTL = 12.
Case 124: 0 nodes not reachable from node 18 with TTL = 13.
Case 125: 0 nodes not reachable from node 18 with TTL = 14.
Case 126: 0 nodes not reachable from node 18 with TTL = 15.
Case 127: 4 nodes not reachable from node 1 with TTL = 0.
Case 128: 3 nodes not reachable from node 1 with TTL = 1.
Case 129: 2 nodes not reachable from node 1 with TTL = 2.
Case 130: 2 nodes not reachable from node 1 with TTL = 3.
Case 131: 4 nodes not reachable from node 2 with TTL = 0.
Case 132: 2 nodes not reachable from node 2 with TTL = 1.
Case 133: 2 nodes not reachable from node 2 with TTL = 2.
Case 134: 2 nodes not reachable from node 2 with TTL = 3.
Case 135: 4 nodes not reachable from node 3 with TTL = 0.
Case 136: 3 nodes not reachable from node 3 with TTL = 1.
Case 137: 2 nodes not reachable from node 3 with TTL = 2.
Case 138: 2 nodes not reachable from node 3 with TTL = 3.
Case 139: 4 nodes not reachable from node 4 with TTL = 0.
Case 140: 3 nodes not reachable from node 4 with TTL = 1.
Case 141: 3 nodes not reachable from node 4 with TTL = 2.
Case 142: 3 nodes not reachable from node 4 with TTL = 3.
Case 143: 4 nodes not reachable from node 5 with TTL = 0.
Case 144: 3 nodes not reachable from node 5 with TTL = 1.
Case 145: 3 nodes not reachable from node 5 with TTL = 2.
Case 146: 3 nodes not reachable from node 5 with TTL = 3.
Case 147: 1 nodes not reachable from node 10 with TTL = 0.
Case 148: 0 nodes not reachable from node 10 with TTL = 1.
Case 149: 0 nodes not reachable from node 10 with TTL = 2.
Case 150: 0 nodes not reachable from node 12 with TTL = 1.
Case 151: 1 nodes not reachable from node 10 with TTL = 0.
Case 152: 0 nodes not reachable from node 10 with TTL = 1.
Case 153: 0 nodes not reachable from node 10 with TTL = 2.

tumburlek · Post by **tumburlek** » Sun Feb 03, 2013 6:42 am

Guys, I am beginner I am getting TLE on this problem. I've spent countless hours on it and I seriously don't know where my mistake is at. It's a very fun problem but I'd like to get an AC. Thank you in advance. And, here is my code:

Code: Select all

import java.util.*;
import java.io.*;
public class ANodeTooFar 
{
	static class InputReader
	{
		private BufferedReader reader;
		private StringTokenizer tokenizer;
		public InputReader()
		{
			reader = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
		}
		public String next()
		{
			while(tokenizer == null || !tokenizer.hasMoreElements())
			{
				try
				{
					tokenizer = new StringTokenizer(reader.readLine());
				}
				catch(IOException e)
				{
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt()
		{
			return Integer.parseInt(next());
		}
	}
	public static void main(String[] args)
	{
		Set<Integer> S = new LinkedHashSet<Integer>(); //This babe, doesn't allow duplicates.
		int caseX = 1;
		boolean[][] G = new boolean[31][31];
		InputReader in = new InputReader();
		int N = in.nextInt();
		while(N != 0)
		{
			for(boolean[] X : G)
				Arrays.fill(X, false);
			for(int i = 0; i < N; i++)
			{
				int x = in.nextInt();
				int y = in.nextInt();
				if(x <= 1 || x >= 30)
					x%=31;
				if(y <= 1 || y >= 30)
					y%=31;
				S.add(x);
				S.add(y);
				G[x][y] = true;
				G[y][x] = true;
			
			}
			int root;
			int TTL, troot = 0;
			root = in.nextInt();
			troot = root;
			if(root <= 1 || root >= 30)
			{
				root%=31;
			}
			TTL = in.nextInt();
			
			while(root != 0 || TTL != 0)
			{
				Set<Integer> X = new LinkedHashSet<Integer>(S);
				int size = getResult(root, TTL, G, X);
				System.out.println("Case " + caseX + ": " + size + " nodes not reachable from node " + troot + " with TTL = " + TTL + ".");
				caseX++;
				root = in.nextInt();
				TTL = in.nextInt();
				troot = root;
				if(root <= 1 || root >= 30)
				{
					root%=31;
				}
			}
			N = in.nextInt();
			S.clear();
		}
		System.exit(0);
		
	}
	static int getResult(int root, int TTL, boolean[][] G, Set<Integer> S)
	{
		
		Map<Integer, Integer> M = new HashMap<Integer, Integer>();
		Queue<Integer> States = new LinkedList<Integer>();
		States.add(root);
		M.put(root, 0);
		while(!States.isEmpty())
		{
			int curr = States.remove();
			S.remove(curr);
			process(S, M, States, TTL, G, curr);
		}
		return S.size();
	}
	static void process(Set<Integer> S, Map<Integer, Integer> M, Queue<Integer> States, int TTL, boolean[][] G, int curr) //Will generate states until depth TTL.
	{
		int parentDepth = M.get(curr);
		int currentDepth = parentDepth + 1;
		for(int i = 1; i <= 30; i++)
		{
			if(G[curr][i])
			{
				int newState = i;
				if(currentDepth > TTL)
					break;
				States.add(newState);
				M.put(newState, currentDepth);
			}
		}
	}
}

brianfry713 · Post by **brianfry713** » Mon Feb 04, 2013 11:34 pm

Use class Main
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

optimization · Post by **optimization** » Mon Feb 18, 2013 8:19 am

Thanks providing these inputs Mohammad Mahmudur Rahman .
I have got my code accepted.

iPameF · Post by **iPameF** » Thu May 30, 2013 8:21 am

Hi everyone, I'm getting Runtime error, but why?

Code: Select all

#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;
#define MS(a, v) memset(a, v, sizeof a)
#define NL 			printf("\n")
#define foreach(IT,C) for(typeof(C.begin())IT=C.begin();IT!=C.end();IT++)

#define MAX_N 1000

vector< vector<int> > graph(MAX_N); 
bool visited[MAX_N];
int dist[10000];

void init_graph(int nodes) {
	 int i;
	 for (i = 0; i < nodes; i++) {
	 	 visited[i] = false;
	 	 graph[i].clear();
	 }
}
void bfs(int start) {
    memset(dist, -1, sizeof dist);
    queue<int>Q;
    Q.push(start);
    dist[start] = 0;
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int j=0 ; j<graph[u].size(); j++) {
            int v = graph[u][j];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                Q.push(v);
            }
        }
    }
}

int main ()
{
	int edges;
	set<int> numbers;
	int cases=0;
	while (scanf("%d",&edges)&&edges)
	{
		init_graph(10000);
		numbers.clear();
		for (int i = 0; i < edges; ++i)
		{
			int a,b;
			cin>>a>>b;
			numbers.insert(a);
			numbers.insert(b);
			graph[a].push_back(b); 
			graph[b].push_back(a); 
		}
		int beg,TTL;
		while(cin>>beg>>TTL)
		{
			int c=0;
			if(beg==0&&TTL==0) break;
			bfs(beg);
			foreach(it,numbers)
			{
				int temp=*it;
				if(dist[temp]>TTL)
				{
					c++;
				}
			}
			printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cases,c,beg,TTL );
		}

	}

}

brianfry713 · Post by **brianfry713** » Wed Jun 12, 2013 1:16 am

The node numbers can be any integer, maybe greater than 1000, use a map.

Skynet094 · Post by **Skynet094** » Sat Aug 24, 2013 9:02 am

Hello, For the AC output given here ..
1
10 11 //Only one edge
//input
1
10 11
10 0 10 1 10 2 12 1 10 0 10 1 10 2 0 0
0

Case 147: 1 nodes not reachable from node 10 with TTL = 0.
Case 148: 0 nodes not reachable from node 10 with TTL = 1. //here the first one
Case 149: 0 nodes not reachable from node 10 with TTL = 2.
Case 150: 2 nodes not reachable from node 12 with TTL = 1.
Case 151: 2 nodes not reachable from node 10 with TTL = 0. //here the second one
Case 152: 1 nodes not reachable from node 10 with TTL = 1.
Case 153: 1 nodes not reachable from node 10 with TTL = 2.

it can be seen that with input (10,0) first the result is 1 and for the second attempt of it (10,0) the result is 2 ... How this can be possible ?

brianfry713 · Post by **brianfry713** » Sat Aug 24, 2013 11:16 am

I corrected the I/O in my previous post

triplemzim · Post by **triplemzim** » Wed Oct 23, 2013 6:57 pm

please help why getting WA???? in problem: 336 , A node too far: here is my code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

int main()
{

	vector<long long int> v[110];
	vector<long long int> :: iterator it;
	map<long long int,int> :: iterator mp;
	queue<long long int> q;
	bool visited[110]={false};
	map<long long int,int> track;
	long long count,dist,last,temp1,temp2,src,top,caseno=1,cost[110],parent[110];

	long long index,nc;
	while(scanf("%lld",&nc)==1 && nc)
	{

		index=1;

		for(int i=0;i<nc;i++)
		{

			scanf("%lld%lld",&temp1,&temp2);
			if(track[temp1])
			{

				v[track[temp1]].push_back(temp2);
			}
			else
			{
				track[temp1]=index;
				v[index++].push_back(temp2);
			}
			if(track[temp2])
			{
				v[track[temp2]].push_back(temp1);
			}
			else
			{
				track[temp2]=index;
				v[index++].push_back(temp1);
			}
		}

		while(scanf("%lld%lld",&src,&dist)==2 && (src || dist))
		{
			count=0;
			q.push(src);

			cost[track[src]]=0;
			while(!q.empty())
			{
				top=q.front();

				visited[ track[top] ]=true;
				for(it=v[ track[top] ].begin();it<v[ track[top] ].end(); it++)
				{
					if(visited[ track[*it] ]==false)
					{

						parent[track[*it]]=track[top];
						cost[track[*it]]= cost[ track[top] ]+1;
						if(cost[track[*it]]>dist) {count++;}
						visited[ track[*it] ]=true;
						q.push(*it);
					}
				}

				q.pop();

			}

			printf("Case %lld: %lld nodes not reachable from node %lld with TTL = %lld.\n",caseno++,count,src,dist);
			q.empty();
			memset(parent,0,sizeof(parent));
			memset(cost,0,sizeof(cost));
			memset(visited,false,sizeof(visited));
		}

		track.clear();
		memset(v,0,sizeof(v));

	}
	return 0;
}

brianfry713 · Post by **brianfry713** » Wed Oct 23, 2013 8:34 pm

Try the I/O I posted in this thread.

triplemzim · Post by **triplemzim** » Sun Oct 27, 2013 10:23 pm

brianfry713 wrote:Try the I/O I posted in this thread.

got AC thanks...

m2h2 · Post by **m2h2** » Fri Nov 15, 2013 7:38 am

16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 1 3 0 0

For problem 336(a node too fer) how (1 3) works because we have no node named 1.
What should be the output for(1 3).

OJ Board

336 - A Node Too Far

Re: 336 WA

Re: 336 WA

Re: 336 WA

Re: 336 WA

Re: 336 WA

Re: 336 WA

Re: 336 A node too far. WA getting mad. Plz someone help

336 RE

Re: 336 RE

Re: 336 WA

Re: 336 WA

Re: 336 WA

Re: 336 WA

Re: 336 WA