Nbrevu

Tuenti Contest 4 (Pablo Moreno)

Jun 20th, 2011
970
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Author: Pablo Moreno Olalla
  3.     Email address: darthbrevu@yahoo.es
  4. */
  5. #include <set>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9. #include <fstream>
  10. #include <sstream>
  11. #include <iostream>
  12. #include <algorithm>
  13.  
  14. using namespace std;
  15.  
  16. //There are two basic options: either the contents of the file are stored in memory, or it is parsed
  17. //each time some data must be found.
  18.  
  19. //Both approaches are quite inefficient in some sense (space/speed), so I choose the spatially inefficient
  20. //code, which is really easy! The program will still be a little heavy in terms of memory usage, which is
  21. //actually not that much of a deal. Several Mb are more than enough.
  22.  
  23. class TaskData  {
  24. public:
  25.     unsigned long long myDuration;
  26.     set<size_t> dependencies;
  27.     long long totalDuration;    //-1 if not set.
  28. };
  29.  
  30. //I'll use a mix of C and C++ syntaxes. That's how I feel the most comfortable.
  31. bool readFile(const string &in,vector<TaskData> &out)   {
  32.     ifstream ifs(in.c_str());
  33.     if (!ifs.is_open()) return false;
  34.     string tmp;
  35.     //Read the number of tasks
  36.     unsigned long long N;   //OK, 32 bits are enough for *this* case, but that won't *always* be true, right?
  37.     do  {
  38.         getline(ifs,tmp);
  39.         if (ifs.fail()||ifs.eof())  {
  40.             ifs.close();
  41.             return false;
  42.         }
  43.     }   while (sscanf(tmp.c_str(),"%Lu",&N)!=1);
  44.     out.resize(static_cast<size_t>(N));
  45.     //Read the duration of each task.
  46.     unsigned long long a,b;
  47.     for (unsigned long long i=0;i<N;++i)    {
  48.         do  {
  49.             getline(ifs,tmp);
  50.             if (ifs.fail()||ifs.eof())  {
  51.                 ifs.close();
  52.                 return false;
  53.             }
  54.         }   while (sscanf(tmp.c_str(),"%Lu,%Lu",&a,&b)!=2);
  55.         if (a!=i)   {
  56.             cout<<"Missing task "<<i<<'!'<<endl;
  57.             ifs.close();
  58.             return false;
  59.         }
  60.         out[i].myDuration=b;
  61.         out[i].totalDuration=-1;
  62.     }
  63.     //Now read the dependencies.
  64.     for (;;)    {
  65.         getline(ifs,tmp);
  66.         if (ifs.eof())  {
  67.             ifs.close();
  68.             return true;
  69.         }   else if (ifs.fail())    {
  70.             ifs.close();
  71.             return false;
  72.         }
  73.         istringstream iss(tmp);
  74.         iss>>a;
  75.         if (iss.fail()) continue;
  76.         for (;;)    {
  77.             iss.ignore(1);  //The comma.
  78.             iss>>b;
  79.             if (iss.fail()) break;
  80.             else out[a].dependencies.insert(b);
  81.         }
  82.     }
  83. }
  84.  
  85. unsigned long long getDuration(vector<TaskData> &data,size_t i) {
  86.     TaskData &td=data[i];
  87.     if (td.totalDuration>=0) return static_cast<unsigned long long>(td.totalDuration);
  88.     unsigned long long maxN=0;
  89.     set<size_t>::const_iterator end=td.dependencies.end();
  90.     for (set<size_t>::const_iterator it=td.dependencies.begin();it!=end;++it) maxN=max(maxN,getDuration(data,*it));
  91.     return td.totalDuration=td.myDuration+maxN;
  92. }
  93.  
  94. int main(int argc,char **argv)  {
  95.     string fn;
  96.     fn=((argc<=1)?"in":string(argv[1]));
  97.     //The following two lines are not strictly necessary, but make the code a little more handy.
  98.     if (argc>=3) freopen(argv[2],"r",stdin);
  99.     if (argc>=4) freopen(argv[3],"w",stdout);
  100.     vector<TaskData> data(0);
  101.     if (!readFile(fn,data)) return -1;  //Couldn't read file.
  102.     size_t i;
  103.     cin>>i;
  104.     if (!cin.fail()&&i<data.size()) cout<<i<<' '<<getDuration(data,i)<<endl;
  105.     do  {
  106.         cin.ignore(1);  //skip commas.
  107.         cin>>i;
  108.         if (!cin.fail()&&i<data.size()) cout<<i<<' '<<getDuration(data,i)<<endl;
  109.         else break;
  110.     }   while (!cin.eof());
  111.     return 0;
  112. }
RAW Paste Data