Submission #291426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
291426	2020-09-05T10:30:14 Z	cig32	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
vector<pair<int,int> >adjlist[100000];
bool visited[100000];
pair<int,int> maxi={0,INT_MAX};
void dfs(int node,int dist_so_far){
    if(visited[node]==false){
        visited[node]=true;
        if(maxi.first<dist_so_far || (maxi.first==dist_so_far && maxi.second>node)){
            maxi={dist_so_far,node};
        }
        for(int i=0;i<adjlist[node].size();i++){
            if(visited[adjlist[node][i].first]==false){
                dfs(adjlist[node][i].first,adjlist[node][i].second+dist_so_far);
            }
        }
    }
}
vector<int>yes;
stack<int>hmph;
void dfs2(int node,int dist_so_far){
    if(visited[node]==false){
        visited[node]=true;
        hmph.push(node);
        if(maxi.first==dist_so_far && maxi.second==node){
            while(hmph.size()){
                yes.push_back(hmph.top());
                hmph.pop();
            }
            reverse(yes.begin(),yes.end());
        }
        for(int i=0;i<adjlist[node].size();i++){
            if(visited[adjlist[node][i].first]==false){
                dfs(adjlist[node][i].first,adjlist[node][i].second+dist_so_far);
            }
        }
        hmph.pop();
    }
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    map<pair<int,int>,int>mp;
    for(int i=0;i<M;i++){
        adjlist[A[i]].push_back({B[i],T[i]});
        adjlist[B[i]].push_back({A[i],T[i]});
        mp[{A[i],B[i]}]=T[i];
        mp[{B[i],A[i]}]=T[i];
    }
    for(int i=0;i<N;i++) visited[i]=false;
    vector<int>starting;
    for(int i=0;i<N;i++){
        if(visited[i]==false){
            dfs(i,0);
            starting.push_back(maxi.second);
            maxi={0,INT_MAX};
        }
    }
    for(int i=0;i<N;i++){
        visited[i]=false;
    }
    vector<pair<int,int> > diameters;
    vector<vector<int> > paths;
    vector<pair<int,int> > maxrecord;
    for(int i=0;i<starting.size();i++){
        dfs(starting[i],0);
        diameters.push_back({starting[i],maxi.second});
        maxrecord.push_back(maxi);
        maxi={0,INT_MAX};
    }
    for(int i=0;i<N;i++){
        visited[i]=false;
    }
    for(int i=0;i<starting.size();i++){
        maxi=maxrecord[i];
        dfs2(starting[i],0);
        paths.push_back(yes);
        yes.clear();
    }
    int ans=0;
    vector<int>segments;
    for(int i=0;i<paths.size();i++){
        ans=max(ans,maxrecord[i].first);
        int good=INT_MAX;
        int sofar=0;
        for(int j=0;j<paths[i].size();j++){
            if(max(maxrecord[i].first-sofar,sofar)<good){
                good=max(maxrecord[i].first-sofar,sofar);
                sofar+=mp[{paths[i][j],paths[i][j+1]}];
            }
            else break;
        }
        segments.push_back(good);
    }
    int d=segments.size();
    sort(segments.begin(),segments.end());
    ans=max(ans,segments[d-1]+segments[d-2]+L);
    ans=max(ans,segments[d-2]+segments[d-3]+2*L);
    return ans;
}

Compilation message

dreaming.cpp:3:1: error: 'vector' does not name a type
    3 | vector<pair<int,int> >adjlist[100000];
      | ^~~~~~
dreaming.cpp:5:1: error: 'pair' does not name a type
    5 | pair<int,int> maxi={0,INT_MAX};
      | ^~~~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:9:12: error: 'maxi' was not declared in this scope
    9 |         if(maxi.first<dist_so_far || (maxi.first==dist_so_far && maxi.second>node)){
      |            ^~~~
dreaming.cpp:12:23: error: 'adjlist' was not declared in this scope
   12 |         for(int i=0;i<adjlist[node].size();i++){
      |                       ^~~~~~~
dreaming.cpp: At global scope:
dreaming.cpp:19:1: error: 'vector' does not name a type
   19 | vector<int>yes;
      | ^~~~~~
dreaming.cpp:20:1: error: 'stack' does not name a type; did you mean 'obstack'?
   20 | stack<int>hmph;
      | ^~~~~
      | obstack
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:24:9: error: 'hmph' was not declared in this scope
   24 |         hmph.push(node);
      |         ^~~~
dreaming.cpp:25:12: error: 'maxi' was not declared in this scope
   25 |         if(maxi.first==dist_so_far && maxi.second==node){
      |            ^~~~
dreaming.cpp:27:17: error: 'yes' was not declared in this scope
   27 |                 yes.push_back(hmph.top());
      |                 ^~~
dreaming.cpp:30:21: error: 'yes' was not declared in this scope
   30 |             reverse(yes.begin(),yes.end());
      |                     ^~~
dreaming.cpp:30:13: error: 'reverse' was not declared in this scope; did you mean 'std::reverse'?
   30 |             reverse(yes.begin(),yes.end());
      |             ^~~~~~~
      |             std::reverse
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:1180:5: note: 'std::reverse' declared here
 1180 |     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
      |     ^~~~~~~
dreaming.cpp:32:23: error: 'adjlist' was not declared in this scope
   32 |         for(int i=0;i<adjlist[node].size();i++){
      |                       ^~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:41:5: error: 'map' was not declared in this scope; did you mean 'std::map'?
   41 |     map<pair<int,int>,int>mp;
      |     ^~~
      |     std::map
In file included from /usr/include/c++/9/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_map.h:100:11: note: 'std::map' declared here
  100 |     class map
      |           ^~~
dreaming.cpp:41:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   41 |     map<pair<int,int>,int>mp;
      |         ^~~~
      |         std::pair
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_pair.h:208:12: note: 'std::pair' declared here
  208 |     struct pair
      |            ^~~~
dreaming.cpp:41:14: error: expected primary-expression before 'int'
   41 |     map<pair<int,int>,int>mp;
      |              ^~~
dreaming.cpp:43:9: error: 'adjlist' was not declared in this scope
   43 |         adjlist[A[i]].push_back({B[i],T[i]});
      |         ^~~~~~~
dreaming.cpp:45:9: error: 'mp' was not declared in this scope
   45 |         mp[{A[i],B[i]}]=T[i];
      |         ^~
dreaming.cpp:49:5: error: 'vector' was not declared in this scope; did you mean 'std::vector'?
   49 |     vector<int>starting;
      |     ^~~~~~
      |     std::vector
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_vector.h:386:11: note: 'std::vector' declared here
  386 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
dreaming.cpp:49:12: error: expected primary-expression before 'int'
   49 |     vector<int>starting;
      |            ^~~
dreaming.cpp:53:13: error: 'starting' was not declared in this scope; did you mean 'static'?
   53 |             starting.push_back(maxi.second);
      |             ^~~~~~~~
      |             static
dreaming.cpp:53:32: error: 'maxi' was not declared in this scope
   53 |             starting.push_back(maxi.second);
      |                                ^~~~
dreaming.cpp:60:17: error: expected primary-expression before 'int'
   60 |     vector<pair<int,int> > diameters;
      |                 ^~~
dreaming.cpp:61:19: error: expected primary-expression before 'int'
   61 |     vector<vector<int> > paths;
      |                   ^~~
dreaming.cpp:62:17: error: expected primary-expression before 'int'
   62 |     vector<pair<int,int> > maxrecord;
      |                 ^~~
dreaming.cpp:63:19: error: 'starting' was not declared in this scope; did you mean 'static'?
   63 |     for(int i=0;i<starting.size();i++){
      |                   ^~~~~~~~
      |                   static
dreaming.cpp:65:9: error: 'diameters' was not declared in this scope
   65 |         diameters.push_back({starting[i],maxi.second});
      |         ^~~~~~~~~
dreaming.cpp:65:42: error: 'maxi' was not declared in this scope
   65 |         diameters.push_back({starting[i],maxi.second});
      |                                          ^~~~
dreaming.cpp:66:9: error: 'maxrecord' was not declared in this scope
   66 |         maxrecord.push_back(maxi);
      |         ^~~~~~~~~
dreaming.cpp:72:19: error: 'starting' was not declared in this scope; did you mean 'static'?
   72 |     for(int i=0;i<starting.size();i++){
      |                   ^~~~~~~~
      |                   static
dreaming.cpp:73:9: error: 'maxi' was not declared in this scope
   73 |         maxi=maxrecord[i];
      |         ^~~~
dreaming.cpp:73:14: error: 'maxrecord' was not declared in this scope
   73 |         maxi=maxrecord[i];
      |              ^~~~~~~~~
dreaming.cpp:75:9: error: 'paths' was not declared in this scope
   75 |         paths.push_back(yes);
      |         ^~~~~
dreaming.cpp:75:25: error: 'yes' was not declared in this scope
   75 |         paths.push_back(yes);
      |                         ^~~
dreaming.cpp:79:12: error: expected primary-expression before 'int'
   79 |     vector<int>segments;
      |            ^~~
dreaming.cpp:80:19: error: 'paths' was not declared in this scope
   80 |     for(int i=0;i<paths.size();i++){
      |                   ^~~~~
dreaming.cpp:81:21: error: 'maxrecord' was not declared in this scope
   81 |         ans=max(ans,maxrecord[i].first);
      |                     ^~~~~~~~~
dreaming.cpp:81:13: error: 'max' was not declared in this scope; did you mean 'std::max'?
   81 |         ans=max(ans,maxrecord[i].first);
      |             ^~~
      |             std::max
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: 'std::max' declared here
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
dreaming.cpp:87:24: error: 'mp' was not declared in this scope
   87 |                 sofar+=mp[{paths[i][j],paths[i][j+1]}];
      |                        ^~
dreaming.cpp:91:9: error: 'segments' was not declared in this scope
   91 |         segments.push_back(good);
      |         ^~~~~~~~
dreaming.cpp:93:11: error: 'segments' was not declared in this scope
   93 |     int d=segments.size();
      |           ^~~~~~~~
dreaming.cpp:94:5: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
   94 |     sort(segments.begin(),segments.end());
      |     ^~~~
      |     std::sort
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:4887:5: note: 'std::sort' declared here
 4887 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
dreaming.cpp:95:9: error: 'max' was not declared in this scope; did you mean 'std::max'?
   95 |     ans=max(ans,segments[d-1]+segments[d-2]+L);
      |         ^~~
      |         std::max
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: 'std::max' declared here
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~