istringstream

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

istringstream

Post by rjhadley » Tue Dec 31, 2002 8:27 pm

Does istringstream work properly?

I submitted two solutions (10227, 10389) which handled multiple input using code like the following:

10389

Code: Select all

// ...

int 
main( void ) 
{
    unsigned int            numInstances;
    string                  line;
    istringstream           iss;
 
    getline( cin, line );
    iss.str( line );
    iss >> numInstances;
    getline( cin, line );   // blank line

    for( unsigned int instance = 0; instance < numInstances; instance++ ) {
        getline( cin, line );
        if( cin.eof() || cin.fail() ) {
            break;
        } // if

        //...

        iss.clear();
        iss.str( line );
        iss >> vertices[ 0 ].first >> vertices[ 0 ].second;     // home
        iss >> vertices[ 1 ].first >> vertices[ 1 ].second;     // school

       //...
And both programs had runtime errors 0.0 seconds:
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.
.

Which suggests that the crash was at the very start of the program, such as reading the number of cases in the multiple input data set.

For both I changed only the input from istringstream to sscanf() and strtol() and they were both accepted. So is something wrong with using istringstream in general with the online judge's environment, or my particular use of it?

Thanks.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

10389 - Subway

Post by _.B._ » Thu Aug 26, 2004 2:20 am

Greetings!
My code for this problem is now over 150 lines long, and I'm still getting WAs :o
I won't ask you to read it (yet :wink:)
Will you please give me some hints on this one?
Ah!, and some critical I/O too :P
Also, is my I/O for this test case alright?:

Input:

Code: Select all

5

0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1

0 0 20000 2000
0 400 10000 400 14000 400 -1 -1
4000 1200 10000 1200 20000 1200 -1 -1

1 1 10001 1001
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1

0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
0 0 10000 999 -1 -1

0 0 0 0
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
Output:

Code: Select all

21

42

21

15

0
Thanks in advance!
_.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10389 : what are the outputs ???

Post by L I M O N » Tue Jan 31, 2006 9:09 pm

pls someone gives the correct outputs of those following data:

Code: Select all

10

18467 41 26500 6334
19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 -1 -1
292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 -1 -1
17673 4664 15141 7711 28253 6868 25547 27644 32662 32757 20037 12859 8723 9741 27529 778 12316 3035 22190 1842 -1 -1

30106 288 8942 9040
19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 12623 24084 19954 18756 11840 4966 7376 -1 -1
13931 26308 16944 32439 24626 11323 5537 21538 16118 2082 22929 16541 4833 31115 4639 29658 22704 9930 13977 2306 -1 -1
31673 22386 5021 28745 26924 19072 6270 5829 26777 15573 5097 16512 23986 13290 9161 18636 22355 24767 23655 15574 -1 -1

12052 4031 1150 27350
16941 21724 13966 3430 31107 30191 18007 11337 15457 12287 27753 10383 14945 8909 32209 9758 24221 18588 6422 24946 -1 -1
27506 13030 16413 29168 900 32591 18762 1655 17410 6359 27624 20537 21548 6483 27595 4041 3602 24350 10291 30836 -1 -1
9374 11020 4596 24021 27348 23199 19668 24484 8281 4734 53 1999 26418 27938 6900 3788 18127 467 3728 14893 -1 -1

22483 24648 2421 17807
14310 6617 22813 9514 14309 7616 18935 17451 20600 5249 16519 31556 22798 30303 6224 11008 5844 32609 14989 32702 -1 -1
3195 20485 3093 14343 30523 1587 29314 9503 7448 25200 13458 6618 20580 19796 14798 15281 19589 20798 28009 27157 -1 -1
20472 23622 18538 12292 6038 24179 18190 29657 7958 6191 19815 22888 19156 11511 16202 2634 24272 20055 20328 22646 -1 -1

4886 26362 28433 18875
29869 20142 23844 1416 21881 31998 10322 18651 10021 5699 3557 28476 27892 24389 5075 10712 2600 2510 21003 26869 -1 -1
17861 14688 13401 9789 15255 16423 5002 10585 24182 10285 27088 31426 28617 23757 9832 30932 4169 2154 25721 17189 -1 -1
19976 31329 2368 28692 21425 10555 3434 16549 7441 9512 30145 18060 21718 3753 16139 12423 16279 25996 16687 12529 -1 -1

17437 22549 12949 19866
193 23195 3297 20416 28286 16105 24488 16282 12455 25734 18114 11701 31316 20671 5786 12263 4313 24355 31185 20053 -1 -1
912 10808 1832 20945 4313 27756 28321 19558 23646 27982 481 4144 23196 20222 7129 2161 5535 20450 11173 10466 -1 -1
12044 21659 26292 26439 17253 20024 26154 29510 4745 20649 13186 8313 4474 28022 2168 14018 18787 9905 17958 7391 -1 -1

3625 10202 4414 26477
9314 25824 29334 25874 24372 20159 11833 28070 7487 28297 7518 8177 17773 32270 1763 2668 17192 13985 3102 8480 -1 -1
29213 7627 4802 4099 30527 2625 1543 1924 11023 29972 13061 14181 31003 27432 17505 27593 22725 13031 8492 142 -1 -1
17222 31286 13064 7900 19187 8360 22413 30974 14270 29170 235 30833 19711 25760 18896 4667 7285 12550 140 13694 -1 -1

21624 2695 2125 28019
26576 21694 22658 26302 17371 22466 4678 22593 23851 25484 1018 28464 21119 23152 2800 18087 31060 1926 9010 4757 -1 -1
32170 20315 9576 30227 12043 22758 7164 5109 7882 17086 29565 3487 29577 14474 2625 25627 5629 31928 25423 28520 -1 -1
6902 14962 123 24596 3737 13261 10195 32525 1264 8260 6202 8116 5030 20326 29011 30771 6411 25547 21153 21520 -1 -1

0 0 0 10
-1 -1

0 0 0 0
100 100 -1 -1
my program gives :

Code: Select all

48

95

81

68

68

31

63

115

0

0
i m getting WA again again

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Apr 04, 2006 4:24 pm

I had a same problem, but I have used sstream so many times, but in this problem, it doesn't work. may be because of some wrong characters at the end of line.
Anyway you can use sstream in other UVA problems without any problem.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Apr 04, 2006 4:27 pm

When I used sstream to read the input, I got WA, now I change it to my own reader, I got accepted, I think sstream does not work here! This may be help you!

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Apr 04, 2006 4:33 pm

All of my outputs from my Accepted solution differ from your ouput, except 9th and 10th, in which my solution crash on them, I think there is no such a testcase in the judge data.
my output is:
  • 61

    109

    94

    101

    85

    31

    78

    123

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Jun 02, 2006 6:00 pm

To LIMON,

I think you haven't understood the problem clearly.

The problem states -
You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres.
:wink: I believe thats the only trick in this problem. Hope you got it.
Ami ekhono shopno dekhi...
HomePage

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10389 - Subway

Post by Articuno » Fri Dec 11, 2009 7:17 pm

Can anyone say what does this line in the problen description means.. I don't get it
You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres.
Help will be appreciated. Thanks
May be tomorrow is a better day............ :)

razor
New poster
Posts: 3
Joined: Wed Oct 19, 2011 6:48 pm

Re: 10389 - Subway

Post by razor » Mon May 07, 2012 10:05 am

it means if you have subway line description like this:
0 0 0 1 1 0 -1 -1
then, you cannot using subway directly from (0,0) to (1, 0) .

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

Re: 10389 - Subway

Post by brianfry713 » Fri Jul 19, 2013 11:47 pm

Input:

Code: Select all

9

18467 41 26500 6334
19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 -1 -1
292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 -1 -1
17673 4664 15141 7711 28253 6868 25547 27644 32662 32757 20037 12859 8723 9741 27529 778 12316 3035 22190 1842 -1 -1

30106 288 8942 9040
19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 12623 24084 19954 18756 11840 4966 7376 -1 -1
13931 26308 16944 32439 24626 11323 5537 21538 16118 2082 22929 16541 4833 31115 4639 29658 22704 9930 13977 2306 -1 -1
31673 22386 5021 28745 26924 19072 6270 5829 26777 15573 5097 16512 23986 13290 9161 18636 22355 24767 23655 15574 -1 -1

12052 4031 1150 27350
16941 21724 13966 3430 31107 30191 18007 11337 15457 12287 27753 10383 14945 8909 32209 9758 24221 18588 6422 24946 -1 -1
27506 13030 16413 29168 900 32591 18762 1655 17410 6359 27624 20537 21548 6483 27595 4041 3602 24350 10291 30836 -1 -1
9374 11020 4596 24021 27348 23199 19668 24484 8281 4734 53 1999 26418 27938 6900 3788 18127 467 3728 14893 -1 -1

22483 24648 2421 17807
14310 6617 22813 9514 14309 7616 18935 17451 20600 5249 16519 31556 22798 30303 6224 11008 5844 32609 14989 32702 -1 -1
3195 20485 3093 14343 30523 1587 29314 9503 7448 25200 13458 6618 20580 19796 14798 15281 19589 20798 28009 27157 -1 -1
20472 23622 18538 12292 6038 24179 18190 29657 7958 6191 19815 22888 19156 11511 16202 2634 24272 20055 20328 22646 -1 -1

4886 26362 28433 18875
29869 20142 23844 1416 21881 31998 10322 18651 10021 5699 3557 28476 27892 24389 5075 10712 2600 2510 21003 26869 -1 -1
17861 14688 13401 9789 15255 16423 5002 10585 24182 10285 27088 31426 28617 23757 9832 30932 4169 2154 25721 17189 -1 -1
19976 31329 2368 28692 21425 10555 3434 16549 7441 9512 30145 18060 21718 3753 16139 12423 16279 25996 16687 12529 -1 -1

17437 22549 12949 19866
193 23195 3297 20416 28286 16105 24488 16282 12455 25734 18114 11701 31316 20671 5786 12263 4313 24355 31185 20053 -1 -1
912 10808 1832 20945 4313 27756 28321 19558 23646 27982 481 4144 23196 20222 7129 2161 5535 20450 11173 10466 -1 -1
12044 21659 26292 26439 17253 20024 26154 29510 4745 20649 13186 8313 4474 28022 2168 14018 18787 9905 17958 7391 -1 -1

3625 10202 4414 26477
9314 25824 29334 25874 24372 20159 11833 28070 7487 28297 7518 8177 17773 32270 1763 2668 17192 13985 3102 8480 -1 -1
29213 7627 4802 4099 30527 2625 1543 1924 11023 29972 13061 14181 31003 27432 17505 27593 22725 13031 8492 142 -1 -1
17222 31286 13064 7900 19187 8360 22413 30974 14270 29170 235 30833 19711 25760 18896 4667 7285 12550 140 13694 -1 -1

21624 2695 2125 28019
26576 21694 22658 26302 17371 22466 4678 22593 23851 25484 1018 28464 21119 23152 2800 18087 31060 1926 9010 4757 -1 -1
32170 20315 9576 30227 12043 22758 7164 5109 7882 17086 29565 3487 29577 14474 2625 25627 5629 31928 25423 28520 -1 -1
6902 14962 123 24596 3737 13261 10195 32525 1264 8260 6202 8116 5030 20326 29011 30771 6411 25547 21153 21520 -1 -1

0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
AC output:

Code: Select all

61

109

94

101

85

31

78

123

21
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: 10389 - Subway

Post by brianfry713 » Sat Jul 20, 2013 12:22 am

Input:

Code: Select all

1

0 0 10000 10000
1 1 2 2 -1 -1
9999 9999 10000 10000 -1 -1
AC output 85

You can't ride the subway between 2 2 and 9999 9999.
Check input and AC output for thousands of problems on uDebug!

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 10389 - Subway

Post by predicate » Thu Mar 12, 2015 9:27 am

Hey,
I am getting the correct answer for all the above given test cases except the one given below,

Code: Select all

1

30106 288 8942 9040
19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 12623 24084 19954 18756 11840 4966 7376 -1 -1
13931 26308 16944 32439 24626 11323 5537 21538 16118 2082 22929 16541 4833 31115 4639 29658 22704 9930 13977 2306 -1 -1
31673 22386 5021 28745 26924 19072 6270 5829 26777 15573 5097 16512 23986 13290 9161 18636 22355 24767 23655 15574 -1 -1
I get 122 for the above test case,

my code is attached below
I have made a directed graph from the given input and then I run dijkstra to get the answer. A particular subway station is connected to the next and previous stations in the same subway line via a 40km/hr fast subway line and to all other stations and the home and school via a 10km/hr walking line. The weight of the edges that I use is the time it takes to go from one vertex to another via walking or using a subway if possible. I cannot understand why this test case is giving the wrong answer while all the others give the correct answer

Code: Select all

#include <bits/stdc++.h>

#define INF 2000000000
#define VISITED 1
#define EXPLORED 0
#define UNVISITED -1

using namespace std;

vector<vector<pair<int,int> > >subway;
vector<vector<pair<int,double> > >adj;
map<pair<int,int>, int>vertex;
int V;

double eucDis(pair<int,int>a, pair<int,int>b) {
  double x = a.first - b.first, y = a.second - b.second;
  double ans = sqrt(x * x + y * y);
  return ans;
}

void getAdj(void) {
  adj.clear();
  adj.resize(V);
  adj[0].push_back(make_pair(1, eucDis(subway[0][0], subway[0][1])/10000*60));
  adj[1].push_back(make_pair(0, eucDis(subway[0][0], subway[0][1])/10000*60));
  int n = subway.size();
  for (int i = 0; i < n; i++) {
    int m = subway[i].size();
    if (i != 0) {
      for (int j = 1; j < m; j++) {
        int u = vertex[make_pair(i, j)], v = vertex[make_pair(i, j - 1)];
        adj[u].push_back(make_pair(v, eucDis(subway[i][j],subway[i][j - 1])/40000*60));
        adj[v].push_back(make_pair(u, eucDis(subway[i][j],subway[i][j - 1])/40000*60));
      }
    }
    for (int j = 0; j < m; j++) {
      for (int a = 0; a < n; a++) {
        if (a == i) {
          continue;
        }
        int l = subway[a].size();
        for (int b = 0; b < l; b++) {
          int u = vertex[make_pair(i, j)], v = vertex[make_pair(a, b)];
          adj[u].push_back(make_pair(v,eucDis(subway[i][j],subway[a][b])/10000*60));
        } 
      }
    }
  }
}

double dijkstra(void) {
  vector<double>dist(V, INF);
  dist[0] = 0;
  priority_queue<pair<int,double>,vector<pair<int,double> >,
                 greater<pair<int,double> > >pq;
  pq.push(make_pair(0, 0));
  while(!pq.empty()) {
    pair<int,double>cur = pq.top();
    pq.pop();
    int u = cur.second, m = adj[u].size();
    double du = cur.first;
    if (dist[u] < du) {
      continue;
    }
    for (int i = 0; i < m; i++) {
      int v = adj[u][i].first;
      double dv = adj[u][i].second;
      if (dist[u] + dv < dist[v]) {
        dist[v] = dist[u] + dv;
        pq.push(make_pair(dist[v], v));
      }
    }
  }
  return dist[1];
}

int main(void) {
  int test;
  bool init = true;
  cin >> test;
  while (test > 0) {
    test -= 1;
    if (init == true) {
      init = false;
    } else {
      cout << endl;
    }
    vector<pair<int,int> >points;
    int x, y;
    subway.clear();
    vertex.clear();
    V = 0;
    for (int i = 0; i < 2; i++) {
      cin >> x >> y;
      points.push_back(make_pair(x, y));
    }
    subway.push_back(points);
    string line;
    getline(cin, line);
    while (getline(cin, line), line != "") {
      stringstream ss(line);
      points.clear();
      while (ss >> x >> y, x != -1 and y != -1) {
        points.push_back(make_pair(x, y));
      }
      subway.push_back(points);
    }
    for (int i = 0; i < subway.size(); i++) {
      for (int j = 0 ; j < subway[i].size(); j++) {
        vertex[make_pair(i, j)] = V++;
      }
    }
    getAdj();
    double ans = dijkstra();
    cout << round(ans) << endl;
  }
  return 0;
}

Post Reply

Return to “Volume 103 (10300-10399)”