Submission #744546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744546	2023-05-18T17:47:25 Z	vjudge1	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include <bits/stdc++.h>

using namespace std;
const int MAX=1e5+10;
const int INF=(1<<30);
vector<pair<int,int> > graph[MAX];
int dist[MAX];
int vis[MAX];
int FindEnd(int start, int status)
{
    queue<int> q;
    int index,max_dist;
    q.push(start);
    vis[start]=status;
    dist[start]=0;
    while(!q.empty())
    {
        int curr=q.front();
        q.pop();
        for(auto neighbour:graph[curr])
        {
            int newidx=neighbour.first;
            int cost=neighbour.second;
            if(vis[newidx]!=status)
            {
                vis[newidx]=status;
                q.push(newidx);
                dist[newidx]=dist[curr]+cost;
                if(max_dist<dist[newidx])
                {
                    max_dist=dist[newidx];
                    index=newidx;
                }
            }
        }
    }
    return index;

}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int ans,tmp,end;
    for(int i=0; i<M; i++)
    {
        int a=A[i];
        int b=B[i];
        int cena=T[i];
        graph[a].push_back({b,cena});
        graph[b].push_back({a,cena});
    }
    vector<int> radius;
    for(int i=0; i<N; i++)
    {
        if(vis[i]==0)
        {
            int y=FindEnd(i,1);
            int x=FindEnd(y,2);
            tmp=end=dist[x];
            if(ans<tmp)
            {
                ans=tmp;
            }
            while(dist[x]>0)
            {
                for(int j=0; j<graph[x].size(); j++)
                {
                    y=graph[x][j].first;
                    if(dist[x]==dist[y]+graph[x][j].second)
                    {
                        x=y;
                        break;
                    }
                }
                tmp=min(tmp,max(dist[x],end-dist[x]));
            }
            radius.push_back(tmp);
        }
    }
    sort(radius.begin(),radius.end());
    if (radius.size() == 2) ans = max(ans,radius[0]+radius[1]+L);
    else if (radius.size() > 2)
    {
        int last = max(radius[0]+radius[1],radius[1]+radius[2]+L);
        last = min(max(radius[1]+radius[0],radius[0]+radius[2]+L),last);
        last = min(max(radius[2]+radius[0],radius[0]+radius[1]+L),last);
        ans = max(ans,last+L);
    }
    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:65:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for(int j=0; j<graph[x].size(); j++)
      |                              ~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int FindEnd(int, int)':
dreaming.cpp:29:17: warning: 'max_dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |                 if(max_dist<dist[newidx])
      |                 ^~
dreaming.cpp:37:12: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     return index;
      |            ^~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:88:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     return ans;
      |            ^~~
/usr/bin/ld: /tmp/ccQfM5dv.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status